WebShaper: Agentically Data Synthesizing via Information-Seeking Formalization

ArXiv: 2507.15061

🎯 Pitch

Existing methods for creating training data for web agents inadvertently bake in reasoning shortcuts because they generate questions after collecting information, causing the answer to mirror the retrieval structure. WebShaper flips this by first formalizing the question's logical scaffolding—decomposing it into set-theoretic knowledge projections—and then using an agent to iteratively compose them into complex, shortcut-free tasks. The resulting models leapfrog all previous open-source agents on GAIA, hitting 60.1% and nearly matching proprietary Deep Research systems.

1. Executive Summary

This paper introduces WebShaper, a formalization-driven data synthesis framework for training information-seeking agents that operates by first structuring tasks through set-theoretic constructs—specifically, Knowledge Projections (KP)—and then using an agentic Expander to iteratively compose these projections into complex multi-hop questions, enabling precise control over reasoning structure and complexity. Evaluated on the GAIA and WebWalkerQA benchmarks with Qwen-2.5 and QwQ backbones, WebShaper achieves state-of-the-art performance among open-sourced information-seeking agents, including a 60.1 average on GAIA with Qwen-2.5-72B—the only open-source method surpassing 60 points and closing the gap with proprietary systems like OpenAI Deep Research. The paper establishes that formalization-driven synthesis outperforms information-driven alternatives across all tested backbones, with reinforcement learning further amplifying gains by +13.5 points on GAIA for the 72B model, while demonstrating that this advantage holds only when the synthesis process systematically avoids redundancy and reasoning shortcuts through layer-wise expansion rather than ad-hoc or sequential question construction.

2. Context and Motivation

The Core Problem: We Don't Know How to Systematically Generate Training Data for Information-Seeking Agents

The fundamental challenge this paper addresses is deceptively simple: how do you create high-quality training data for LLM-powered agents that search the web to answer complex questions? These "information-seeking" (IS) agents represent one of the most practically important applications of modern language models—they power systems like OpenAI's Deep Research, Gemini Deep Research, and Perplexity—but their development is bottlenecked by a severe scarcity of suitable training data. Unlike standard question-answering, where you can scrape existing datasets or have humans write question-answer pairs, IS tasks require questions whose answers demand multi-step web navigation, cross-source synthesis, and non-trivial reasoning. Such questions are difficult to crowdsource because they require domain expertise to construct, verify, and calibrate for difficulty. The paper argues that this data scarcity is not merely an inconvenience—it is the primary obstacle to developing capable open-source information-seeking agents that can rival proprietary systems.

This matters for several reasons that the paper implicitly highlights:

• Democratization of search-capable AI: Proprietary systems like OpenAI Deep Research achieve 67.4% average on GAIA (Table 1), while the best open-source agentic framework prior to this work (WebDancer with QwQ-32B) reached only 51.5%. The gap is largely a data gap—the proprietary systems are trained on vast, carefully constructed interaction datasets that are not publicly available. Closing this gap requires methods for generating training data that don't depend on proprietary infrastructure or expensive human annotation.

• Controllability of agent capabilities: When you train an agent on whatever data you can scrape or crowd-source, you have little control over what reasoning patterns it learns. The agent might succeed on questions with linear reasoning chains but fail when asked to combine information across three independent constraints, because such patterns were underrepresented in its training data. A systematic data synthesis method would allow deliberate engineering of the reasoning curriculum—exposing the agent to precisely the types and complexities of reasoning you want it to master.

• Bootstrapping reinforcement learning: The modern agent development pipeline—supervised fine-tuning (SFT) followed by reinforcement learning (RL)—depends critically on the quality of the initial SFT data (Section 1: "The entire development of the IS agent originates from and its ultimate effectiveness depends on high-quality IS task training data"). RL can optimize behavior within the neighborhood of the SFT policy, but it cannot invent entirely new reasoning strategies if the initial training data never demonstrated them. The SFT dataset is the foundation; if it's weak, RL amplifies its weaknesses rather than transcending them.

The Information-Driven Paradigm and Its Failures

Prior to WebShaper, existing approaches to synthesizing IS training data followed what the paper terms an information-driven paradigm (Section 1, Figure 2a). The procedure is:

1. Freely search the web and collect interesting or interconnected information—web pages, Wikipedia articles, linked documents.
2. Organize the collected information into some structure—linear chains (WebDancer's CRAWLQA, Wu et al., 2025a), graphs connected via hyperlinks (WebWalkerQA, Wu et al., 2025b), or entity coreference networks (WebSailor's SailorFog-QA, Li et al., 2025a).
3. Prompt an LLM to generate a natural language question whose answer is derivable from the collected information structure.
4. (Optionally) verify the generated question-answer pair for correctness.

The paper identifies two critical failure modes in this approach:

First, structural inconsistency between the collected information and the generated question. The LLM tasked with generating questions may not fully comprehend the information structure it's given—especially when that structure is complex or implicit. As a result, the generated question's reasoning structure (what an agent must actually do to answer it) may not match the information structure (what was collected). For example, the collected web pages might support a three-hop reasoning chain (entity A → B → C → D), but the LLM might generate a question that inadvertently creates a reasoning shortcut—perhaps providing information about D directly in the question context, or connecting A to D without requiring intermediate hops. The question-answer pair that results may be superficially plausible but does not require the intended reasoning depth when an agent actually attempts to solve it.

The paper formalizes this concern more precisely through the concept of reasoning shortcuts (Section 3.2.2). In a sequential expansion structure (Figure 4b), an expansion might add a Knowledge Projection that connects a constant directly to the target variable, allowing the model to "guess the answer by only reasoning on the closer constants and neglecting the deeper sequence." The generated question looks complex (it contains many facts), but the underlying reasoning graph has a short path from question to answer that bypasses the intended multi-hop structure. This is not merely a theoretical possibility—it is a systematic consequence of having the LLM generate questions from information without a formal representation of the desired reasoning topology.

Second, redundancy and homogeneity in collected information. Without a formal task specification guiding what information to collect, the pre-search phase tends to gather information structures that are similar to each other. If you crawl Wikipedia following hyperlinks, you'll encounter certain structural patterns repeatedly—biographical articles link to other biographical articles, geographic articles link to nearby locations, historical events link to related events. The resulting question distribution will over-represent these patterns while under-representing rarer but equally important reasoning structures (e.g., questions requiring synthesis across sports, politics, and science domains simultaneously). The paper refers to this as limited "knowledge coverage" (Section 1): the information-driven approach is inherently constrained by whatever structural diversity happens to emerge from web crawls, rather than systematically exploring the space of possible reasoning patterns.

Additionally, the pre-search phase collects excessive redundant information. When you freely crawl the web without a target question, you accumulate large volumes of content, much of which ends up unused or contributes only trivially to the generated questions. This is computationally wasteful and doesn't translate into proportionally more diverse or challenging training examples.

A subtler but important limitation: the information-driven paradigm offers no principled way to control question difficulty. You can collect information chains of different lengths, but length is a crude proxy for difficulty—a 5-hop question where each hop is a simple look-up may be easier than a 2-hop question requiring synthesis of contradictory sources. Without a formal model of task structure, you cannot parameterize complexity along dimensions that matter for agent training.

How WebShaper Positions Itself: The Formalization-Driven Alternative

WebShaper inverts the synthesis pipeline entirely (Figure 2b). Rather than collecting information first and hoping the generated question has the right structure, it formalizes the desired reasoning structure first using set-theoretic constructs, then uses that formalization to guide what information to collect and how to compose it into a question. The paper draws an explicit analogy to other domains where formalization has proven transformative (Section 1 and Section 5.2):

• In mathematical theorem proving, formal languages like Lean 4 (Moura & Ullrich, 2021) enable systematic synthesis of training data by translating natural language problems into formal statements, generating proofs, and verifying correctness mechanically. Systems like DeepSeek-Prover (Xin et al., 2024) and Goedel-Prover (Lin et al., 2025) leverage this to train provers that iteratively improve.
• In knowledge base question answering (KBQA), formal logic (propositional logic or first-order logic) enables systematic generation of complex queries by composing logical operations, as in LACT (Xia et al., 2025), which uses binary tree decomposition to construct arbitrary first-order logical queries for curriculum learning.

The key insight is that information-seeking tasks lack such an established formalization. Unlike math (where you have Lean 4) or KBQA (where you have propositional logic over knowledge graphs), there is no standard mathematical language for describing what makes one web search question harder than another, or what reasoning topology a question requires. The paper claims to be the first to derive such a formalization based on set theory (Section 1), and this formalization is what makes the entire synthesis pipeline possible.

The formalization's role is not merely descriptive—it is generative and prescriptive. It provides:

1. A vocabulary for specifying reasoning structure: Instead of saying "generate a hard question about sports," you can specify a question as the intersection of three Knowledge Projections with nested sub-queries, each with specific relation types and entity constraints. The reasoning topology is explicit in the formal representation, not implicit in the collected information.

2. A mechanism for systematic exploration: By composing Knowledge Projections through union and intersection operations, you can enumerate the space of possible question structures and sample from it systematically, ensuring broad coverage of reasoning patterns. The paper's domain distribution (Figure 5) shows coverage across sports, politics, entertainment, and other domains—not because the web crawl happened to yield those distributions, but because the formalization-guided expansion process deliberately constructs questions spanning diverse topics.

3. A framework for controllable complexity: The "number of expanding layers" (Section 3.2.2) is a hyperparameter that directly controls the depth of the reasoning graph. The layer-wise expansion strategy (Section 3.2.2) ensures that each layer adds genuine reasoning depth without introducing redundancy or shortcuts. This is not possible in information-driven approaches where complexity is an emergent property of whatever the LLM happens to generate from the collected content.

4. Verifiability: Because questions have a formal representation, you can mechanically check whether the generated question-answer pair is structurally consistent (does the answer entity actually satisfy all the constraints specified in the formalization?) and whether the question avoids trivial shortcuts (does the graph have the intended depth?). The paper's Validate tool (Section 3.2.3) implements two specific checks: (a) that the type of the answer entity satisfies the sub-question's constraints, and (b) that the sub-question cannot be answered directly by an LLM without web search. These validation steps are possible precisely because the formal representation makes the intended reasoning structure explicit.

Reconciling Conflicting Design Constraints

The paper's approach must resolve an inherent tension: the formalization needs to be expressive enough to capture the diversity of real information-seeking tasks (which involve arbitrary relations, nested conditions, temporal constraints, etc.) while being simple enough that an LLM-based agent (the Expander) can reliably manipulate it during synthesis. The Knowledge Projection formalism with set-theoretic union and intersection achieves this balance through two key design choices:

First, the representation reduces all operations to triplets. By Proposition 1 (Section 3.2.1), R-Union distributes over set union, meaning that $R(S_1) \cup R(S_2)$ can be represented as $R(S_1 \cup S_2)$. This eliminates union as a separate operation in the representation—everything becomes intersections of triplets of the form $[X, r, S]$. This is not merely a notational convenience; it means the Expander agent only needs to understand one compositional operation (intersection) rather than two, reducing the cognitive burden on the LLM during synthesis.

Second, recursion is flattened into a flat list of constraints. A nested expression like $R_1(R_2(S))$ would be hard for an LLM to manipulate reliably. By introducing named variables (e.g., $V@X$, $V@Y$), recursive structures become a flat list of triplets: $[[V@X, r_1, V@Y], [V@Y, r_2, S]]$. The variable binding makes the dependency explicit without requiring the Expander to reason about nested function application. This is a pragmatic concession to LLM capabilities: the formal semantics are preserved, but the surface representation is optimized for reliable machine manipulation.

The paper's position is thus: formalization is necessary but must be engineered for the synthesizer, not just for human understanding. This distinguishes WebShaper from purely theoretical formalization exercises—the formalism is designed to be operationalized by an LLM-based agent during the synthesis loop.

Connecting to the Empirical Findings

The motivation is validated empirically in Section 4.3.4 (Figure 7a), where the formalization-driven synthesis ("FL") consistently outperforms a natural-language variant ("NL") across all backbones (Qwen-2.5-32B, Qwen-2.5-72B, QwQ-32B). The paper interprets this as evidence that formalization "mitigates the limitations incurred by natural language"—specifically, it reduces error propagation during synthesis and enables generation of question types that natural language prompting alone cannot reliably produce.

Similarly, the layer-wise strategy's advantage over sequential expansion (Section 4.3.5, Figure 7b) demonstrates that the structure of expansion matters independently of the formalization—even with formal representations, expanding questions in a sequential chain introduces shortcuts that a layer-wise traversal avoids. The tool call analysis (Section 4.3.6, Figure 8) further corroborates this: WebShaper-trained agents execute significantly more search operations, visit more pages, and sustain longer tool-call sequences than agents trained on information-driven datasets (E2HQA, MHQA), suggesting that the formalization-driven data genuinely teaches more complex, multi-hop reasoning behaviors rather than superficial pattern matching.

In summary, WebShaper addresses a gap that is simultaneously practical (no high-quality open-source IS training data exists at the scale needed), methodological (no formal framework exists for describing IS task structure), and engineering (existing synthesis methods produce structurally inconsistent data). Its contribution is not a single technique but a pipeline architecture built around the insight that formal task specification must precede information collection, not follow it.

3. Technical Approach

3.1 Reader Orientation

This paper presents a data synthesis pipeline — a system that automatically generates training examples (question-answer pairs plus agent trajectories) for teaching language models how to search the web and reason across multiple information sources to answer complex questions. The system solves the problem of how to create a large, diverse, structurally correct dataset of information-seeking tasks without human annotation, by first mathematically formalizing what an information-seeking task is (using set theory) and then using an LLM-based agent to systematically compose these formal structures into increasingly complex questions, validating each step against the formalization to prevent structural errors.

3.2 Big-Picture Architecture (Diagram in Words)

The WebShaper pipeline has five major stages executed sequentially:

1. Seed Task Construction — generates an initial pool of ~18,000 diverse, relatively simple information-seeking questions from Wikipedia content, using random walks across linked articles and LLM-based question generation.
2. Task Formalization — represents every question as a formal expression using Knowledge Projections (KP) — set-theoretic units capturing entity sets under relations — composed via intersection ($\cap$) and R-Union ($\cup$) operations. This formalization is the "skeleton" that guides all subsequent synthesis.
3. Agentic Expansion — iteratively makes questions more complex by taking the formal representation of a current question, identifying its "leaf constants" (terminal entity sets in the reasoning graph), and for each leaf constant, invoking an Expander agent that searches the web for information about that constant, formulates a sub-question whose answer is that constant, and merges the sub-question back into the main question. This process respects a layer-wise strategy to avoid adding redundant or shortcut-creating constraints.
4. Trajectory Construction — takes the expanded (complex) questions and uses a separate ReAct agent to solve them, producing step-by-step trajectories (thought-action-observation sequences). Only correct trajectories that pass quality filters are retained, yielding 5,000 training trajectories.
5. Agent Training — uses the collected trajectories for supervised fine-tuning (SFT) followed by reinforcement learning (GRPO) to train the final information-seeking agent model.

Information flows as follows: Wikipedia articles → seed questions → formal representations → expanded formal representations (via web-searching Expander) → natural language questions → agent rollouts → filtered trajectories → trained model. The formalization sits at the center, constraining every generative step.

3.3 Roadmap for the Deep Dive

• First, the IS task formalization (Section 2 of the paper), because it is the mathematical foundation that makes the entire pipeline possible — without it, systematic expansion, validation, and structural correctness guarantees are impossible.
• Second, the seed question construction process (Section 3.1), since the expansion process needs an initial set of questions to start from.
• Third, the KP representation (Section 3.2.1), which bridges the gap between the abstract set-theoretic formalization and the concrete prompt format that the Expander LLM receives.
• Fourth, the layer-wise expansion strategy (Section 3.2.2), which is the algorithm that determines which constants to expand at each iteration and why the resulting structures avoid redundancy and reasoning shortcuts.
• Fifth, the Expander agent internals (Section 3.2.3), including its tools, its validation procedure, and how it autonomously retrieves and structures knowledge to create sub-questions.
• Sixth, the trajectory construction and filtering process (Section 3.3), which converts expanded questions into training data.
• Seventh, the training procedure (Section 3.4), covering SFT loss masking and GRPO optimization.

3.4 Detailed, Sentence-Based Technical Breakdown

This is primarily a methods and systems paper whose core idea is that information-seeking task synthesis can be made principled, controllable, and structurally sound by formalizing IS tasks in set theory and using that formalization to drive an agentic expansion process, rather than relying on ad-hoc post-hoc question generation from retrieved content.

Information-Seeking Task Formalization (Set-Theoretic Foundation)

The paper introduces a formal language for describing information-seeking tasks. The central concept is the Knowledge Projection (KP), which models a single "hop" in an information retrieval chain.

Let $\mathcal{E}$ be the universal set of all entities — players, teams, years, books, authors, locations, etc. Let $R \subseteq \mathcal{E} \times \mathcal{E}$ be a relation — a set of ordered pairs of entities where a specific semantic relationship holds. For instance, if $R$ is the bornIn relation, then $(person, year) \in R$ means the person was born in that year.

A Knowledge Projection $R(V)$ is defined as:

$R(V) = \{u \mid \exists v \in V, (u, v) \in R \text{ or } (v, u) \in R\}$

where $V \subseteq \mathcal{E}$ is a subset of entities (the "source set"), and $R$ is a relation.

What it computes: Given a set of source entities $V$ and a relation $R$, the KP $R(V)$ returns all entities $u$ that have the relation $R$ to any entity in $V$, in either direction. The direction-insensitivity (the or clause) is important: if $R$ is bornIn, then $R(\{1990\})$ returns all people born in 1990 (where the person entity appears first in the pair), while $R(\{Einstein\})$ returns the year 1879 (where the year entity appears second). This bi-directionality captures the fact that IS queries can traverse relations in either direction — you might look up a person's birth year or find all people born in a given year.

Why this form: The definition explicitly avoids requiring a directed knowledge graph with fixed subject-to-object orientation. Real web information doesn't come pre-structured as a directed graph — a Wikipedia article about 1990 lists people born that year (entity → people), while a biographical article lists the person's birth year (person → entity). The KP formalism handles both naturally via the symmetric or condition, making it a more realistic model of web-based information seeking than directed graph formalisms.

Operations on Knowledge Projections:

Two operations compose KPs into more complex queries:

R-Union ($\cup$): When the query condition involves a range or a disjunction of values for the same relation. Formally:

$R(V) = R(S_1) \cup R(S_2) \cup \dots \cup R(S_m)$

where $V = S_1 \cup S_2 \cup \dots \cup S_m$. This captures cases like "players who played in any year between 2000 and 2010" — the source set $V$ is $\{2000, 2001, \dots, 2010\}$, and the R-Union is $R_{playAt}(\{2000\}) \cup \dots \cup R_{playAt}(\{2010\})$.

Why this form: The explicit union decomposition models how an IS agent must work in practice: it cannot query "players in 2000-2010" as a single atomic operation; instead, it must search for each year (or a summarized page covering the range) and union the results. The formalization makes this decomposition explicit, which is critical for generating training data that teaches the agent to perform such decomposition.

Intersection ($\cap$): When the target entity must simultaneously satisfy multiple independent constraints. Formally:

$R(V) = R_1(S_1) \cap R_2(S_2) \cap \dots \cap R_n(S_n)$

where each $R_i$ is a different relation (e.g., playAt and bornIn). For instance, $R_{playAt}(\{2000\}) \cap R_{bornIn}(\{90s\})$ yields players who both played in 2000 and were born in the 90s.

Why this form: Intersection is the mathematical operation that creates multi-hop reasoning complexity. Single-KP questions are simple look-ups; questions requiring intersection of $n$ KPs require the agent to independently resolve $n$ constraints and then find the entities satisfying all of them. The number of intersecting KPs directly controls the reasoning complexity of the task — a key design lever that the information-driven paradigm lacks.

Recursive Target Definition:

An IS task defines a target set $T$ — the entities that answer the question. $T$ can be defined directly:

$T = \bigcap_{i=1}^p (R_i(S_{i,1}) \cup R_i(S_{i,2}) \cup \dots \cup R_i(S_{i,t_i}))$

where each $S_{i,j} \subset \mathcal{E}$ is an entity set (possibly a singleton, possibly a union). This reads: $T$ is the intersection of $p$ conjunctive conditions, where the $i$-th condition is the R-Union of KPs over source sets $S_{i,1}, \dots, S_{i,t_i}$ under relation $R_i$.

What it computes: The outer intersection over $i = 1, \dots, p$ means the answer must satisfy all $p$ conditions simultaneously. Each condition $i$ is itself an R-Union, allowing any condition to involve a disjunction over multiple source sets (e.g., "played in 2004 or 2005").

More powerfully, $T$ can be recursively defined by replacing source sets with other target sets:

$T = R_1(T_1) \cap R_2(T_2) \cap \dots \cap R_k(T_k)$

where each $T_j$ is itself a target set defined by its own intersection of KPs. This recursion is what enables multi-hop questions: to find $T$, you must first find $T_1, \dots, T_k$ (the intermediate entities), then use them as sources for the KPs that define $T$.

An IS task is then simply:

$q(T) \triangleq ?T$

What it computes: The question $q(T)$ asks: "what entities are in the set $T$?" The formalization doesn't specify how to find them — it specifies what must be found and under what constraints. The question text is a natural language rendering of this formal specification.

Why this form: This formalization separates the specification of the task (what the answer must satisfy) from the process of solving it (web search, reasoning, synthesis). This separation is the key insight that enables systematic data synthesis: you can generate valid task specifications by composing KPs, validate them mechanically, and then separately generate solving trajectories. Information-driven approaches conflate these two — the question is generated from retrieved content, so the specification is the retrieval process, making it impossible to systematically vary one while controlling the other.

Worked Example (Figure 3):

The paper illustrates the formalization with the question: "Which player of a team in the 2004-05 season, who was born in 90s? This team is founded in 1966 and is an East German football team."

The formal representation is:

Walkthrough: $T_1$ is the intermediate target: entities that are both founded in 1966 and are East German football teams — this resolves to {Berliner FC Dynamo}. Then $T$ is the intersection of three constraints: (1) players who played in $T_1$ (the team), (2) players who played at 2004 or 2005 (the season), and (3) players born in any year from 1900 to 1999 (the 90s range — the paper's notation $\bigcup_{1900}^{1999}$ represents the R-Union over 1990-1999). The answer set is $\{$Robert Rudwaleit, Danny Kukulies, ...$\}$.

Why this decomposition: The recursive structure explicitly captures the reasoning dependency: you cannot find the players without first identifying the team. The formalization makes this dependency a structural property of the expression, not an implicit consequence of how the question is phrased. During synthesis, this enables mechanical validation — you can check that $T_1$ is well-defined (its source sets are known constants) and that $T$'s KPs properly reference $T_1$.

Seed Question Construction (Section 3.1)

The first stage of the pipeline generates ~18,000 relatively simple seed questions from Wikipedia. This provides the initial "base" of the expansion tree.

Procedure:

1. Offline Wikipedia database construction. The authors download all URLs corresponding to Wikipedia articles, preserving hyperlinks between them. This creates a local copy of the Wikipedia link graph.

2. Random walk and content aggregation. The system performs random walks across the link graph — starting at an arbitrary article, following a hyperlink to another article, then another, and so on. The content from all articles visited during a walk is aggregated into a single context document.

3. LLM-based question generation. An LLM (the paper does not specify which model for this stage, but the agent in later stages is based on QwQ-32B) is prompted to generate a question-answer pair that is "entirely grounded in the content from the collected articles, without relying on external knowledge sources" (Section 3.1). The critical constraint is that the answer must be derivable solely from the aggregated article content, ensuring the question is answerable given the right web navigation.

4. Filtering via rollout verification. The generated seed questions are noisy and may contain hallucinations (questions whose answers aren't actually supported by the article content). To filter these, each seed question $q^1(T)$ is given to the WebDancer agent framework (Wu et al., 2025a) running the QwQ model (Team, 2025), which performs 5 independent rollouts — 5 complete web-search-and-reasoning trajectories attempting to answer the question. A seed question is retained only if at least one of the 5 rollouts produces the correct answer. This filtering criterion is intentionally lenient: it only requires that the question is potentially answerable by an agent, not that the agent consistently answers it correctly.

Why 18,000 seeds? The paper doesn't provide an explicit justification for this number, but it likely reflects a trade-off: more seeds provide broader coverage of the topic and relation space, but the expansion process multiplies the computational cost (each seed spawns multiple expansion steps, each requiring web searches and LLM calls). 18,000 is large enough to achieve the domain diversity shown in Figure 5 (sports, politics, entertainment, etc.) while remaining computationally tractable.

Why random walks? This approach produces question-relevant content sets that have inherent multi-hop structure — the hyperlinks that connect the articles during the walk naturally encode relationships between entities. An LLM generating questions from a sequence of linked articles is likely to produce questions that require traversing those links, creating an implicit information chain. This makes the seed questions structurally aligned with the KP-based formalization that follows, even though they were generated without formal guidance.

Why the WebDancer filtering step? Direct LLM judgment of question quality is unreliable — the LLM might hallucinate that a question is answerable when it isn't. By actually running an agent and checking whether it can find the answer, the filter provides a behavioral signal of answerability. The 1-out-of-5 threshold is deliberately low to avoid discarding questions that are merely challenging rather than impossible.

KP Representation (Section 3.2.1)

The abstract set-theoretic formalization from Section 2 is not directly usable as a prompt for an LLM-based Expander — LLMs operate on tokens, not mathematical expressions with quantifiers and set-builder notation. The paper introduces a KP Representation that translates the formalization into a structured format the Expander agent can reliably parse and generate.

Core elements:

• Constant: A subset of $\mathcal{E}$ defined by explicitly listing its elements, represented in prompts with the prefix @C followed by a natural language description. Example: C@2004_05 represents the set {2004, 2005}. The underscore notation is a shorthand for set union: 2004_2005 means $\{2004\} \cup \{2005\}$.
• Variable: A subset of $\mathcal{E}$ whose elements are not explicitly given, represented with the prefix V@ followed by a name. Example: V@T is the target variable (the answer to the question). Variables act as symbolic placeholders that get bound to entity sets when the question is solved.

Triplet representation of a single KP: A KP $R(S)$ is represented as a triplet $[X, r, S]$, where:

• $X$ is a Variable — the result of the projection (the entities being projected to).
• $r$ is the relation name as a natural language string — playIn, bornIn, foundIn, isA, etc.
• $S$ is either a Variable or a Constant — the source set of the projection.

What this triplet means operationally: "Find the set of entities $X$ that have relation $r$ to entities in set $S$." For example, [V@T, bornIn, C@90s] means "$T$ is the set of entities born in the 90s." Note that $X$ is the output of the projection — for $R(S)$, $X$ is $R(S)$.

Handling Intersection: A conjunction of $n$ KPs on the same target variable is naturally represented as a list of triplets sharing the same first element $X$:

$[[X, r_1, S_1], [X, r_2, S_2], \dots, [X, r_n, S_n]]$

This reads: "$X$ must be in $R_1(S_1)$ AND in $R_2(S_2)$ AND ... AND in $R_n(S_n)$." The shared $X$ enforces that all constraints apply to the same entity set.

Handling R-Union via Proposition 1: Rather than representing R-Union as a separate list-of-lists (which would complicate the representation when unions and intersections are nested), the paper proves and exploits a distributive law:

Proposition 1. For a given relation $R$, $R$-union distributes over set union:

$R(S_1) \cup R(S_2) = R(S_1 \cup S_2)$

Proof sketch (included in paper, Section 3.2.1): If an entity $x$ is in $R(S_1) \cup R(S_2)$, there exists some $y$ in either $S_1$ or $S_2$ such that $(x, y) \in R$ or $(y, x) \in R$. Therefore $y$ is in $S_1 \cup S_2$, so $x \in R(S_1 \cup S_2)$. Conversely, if $x \in R(S_1 \cup S_2)$, then there exists $y \in S_1 \cup S_2$ with the appropriate relation pair, placing $x$ in either $R(S_1)$ or $R(S_2)$. The two sets are therefore equal.

Practical consequence: The R-Union of KPs with the same relation $r$ can be represented by simply merging their source sets. In the triplet notation, rather than having multiple triplets $[X, r, S_1], [X, r, S_2], \dots$, you have a single triplet $[X, r, S_1 \cup S_2 \cup \dots]$. In prompts, this merged set is expressed with underscores (e.g., C@2004_2005) or with natural language descriptions (e.g., C@90s for $\{1990, 1991, \dots, 1999\}$).

Why this matters: The distributive law collapses R-Union into the source set, meaning the KP representation only needs to explicitly represent intersection of triplets with different relations. All unions of the same relation are absorbed into the constant descriptions. This dramatically simplifies the representation that the Expander agent must manipulate — it sees a flat list of triplets, not a tree of nested union-intersection expressions.

Handling Recursion: A recursive target definition $T = R_1(T_1) \cap R_2(T_2)$ where $T_1 = R_3(S)$ is represented by flattening: each intermediate variable ($T_1$) appears as both an output of some triplets and an input (source) to others. The full representation is a list of all triplets with shared variables linking them. For instance:

$[[V@T, r_1, V@T_1], [V@T, r_2, V@T_2], [V@T_1, r_3, S]]$

What this computes: $V@T$ depends on $V@T_1$ (which in turn depends on $S$ via relation $r_3$) and on $V@T_2$. The dependency graph is implicit in the variable co-occurrence — $V@T_1$ appears as the first element of the third triplet (where it is the output) and as the third element of the first triplet (where it is the input). This "threading" of variables through the triplet list is what replaces explicit function composition.

Why this form: The flat list representation avoids requiring the Expander LLM to parse or generate nested expressions. The variable-binding convention makes the dependency structure explicit in a linear token sequence, which is far easier for an autoregressive LM to handle reliably than parenthesized nested function calls. The trade-off is that the flat representation is slightly less compact — a deeply nested expression becomes a long list of triplets — but for the scale of questions the paper targets (a handful of hops), this is a non-negligible versus catastrophic complexity difference for the LLM.

Full worked example: The question from Eq. (1) becomes in KP representation:

[[V@T, playIn, V@X],
 [V@T, playAt, C@2004_05],
 [V@T, bornIn, C@90s],
 [V@X, foundIn, C@1966],
 [V@X, isA, C@East German football team]]

This is a list of 5 triplets. $V@T$ is the target: it must satisfy playIn V@X, playAt 2004_05, and bornIn 90s simultaneously. $V@X$ is an intermediate variable: it must satisfy foundIn 1966 and isA East German football team. The constants C@2004_05, C@90s, C@1966, and C@East German football team are leaf nodes — explicitly specified entity sets. The structure is bipartite between variables and constants: each triplet connects a variable to another variable or to a constant via a relation.

Layer-wise Expansion Strategy (Section 3.2.2)

Given a seed question (formalized as a list of triplets), the expansion process iteratively makes the question more complex. The key design question is: which constants should be expanded at each step, and in what order?

The paper frames this as a graph traversal problem. The KP representation can be viewed as a graph (Figure 4):

• Variables are nodes (including the target variable $T$).
• Constants are leaf nodes (no outgoing edges — they are explicitly specified entity sets).
• Edges are labeled by relations, connecting a variable to either another variable or a constant.

Structural pathologies in alternative expansion strategies:

The paper identifies two baseline expansion strategies and their failure modes (Figure 4):

• Random Structure (Figure 4a): At each expansion step, randomly pick any constant and expand it by adding new triplets that make that constant a variable dependent on new constants. The resulting graph can contain redundancy: constants connected directly to other constants (creating edges between leaf nodes). In natural language, this produces sentences like "Dynamo Berlin is a football club based in Berlin" — factual statements that don't increase the reasoning depth required to answer the question (the fact is given directly, no search needed). From a graph perspective, these are edges that don't contribute to the distance between any leaf constant and the target variable — they add bulk without adding reasoning hops.

• Sequential Structure (Figure 4b): Expand by picking the most recently added constant (or the constant closest to the target along some path) and expanding it. This creates a chain-like structure. The pathology is reasoning shortcuts: a Knowledge Projection may be added that directly connects a constant to the target variable, creating a short path from leaf to root that bypasses intermediate hops. The model can then "guess the answer by only reasoning on the closer constants and neglecting the deeper sequence" (Section 3.2.2). The question text may contain many constraints, but one of them provides a direct path to the answer, making the multi-hop structure superficial.

Layer-wise strategy:

The layer-wise strategy (Figure 4c) avoids both pathologies by enforcing a disciplined expansion order:

1. Identify all leaf constants in the current graph. A leaf constant is a constant that is not referenced as the output (X) of any triplet — it appears only as a source (S) in triplets.
2. Traverse the graph layer by layer from the target variable outward. The first layer consists of constants directly connected to the target. The second layer consists of constants connected to variables that are connected to the target, and so on.
3. At each expansion step, select one leaf constant (presumably from the deepest layer first, though the paper doesn't explicitly specify the selection order among same-layer leaves). The Expander agent takes this constant $C$ and:
   • Retrieves information about $C$ from the web.
   • Constructs a sub-question for which $C$ is the answer.
   • Replaces $C$ in the original question's triplet list with a new variable $V_{new}$, and adds the triplets defining the sub-question (which make $V_{new}$ depend on new constants).
4. The expanded question always has the same answer as the original question (Section 3.2.2: "Note that the $q^{n+1}(T)$ always has the same answer as $q^n(T)$"). The expansion doesn't change what the target set is; it only changes how many intermediate reasoning steps are required to find it.
5. Repeat for the next leaf constant (or terminate when a target number of expansion layers $l$ is reached).

Why layer-wise prevents redundancy: By construction, the expansion always replaces a constant with a variable connected to new constants. The new constants are "further" from the target than the original constant was. The edge between the new variable and the original constant's neighbors is a meaningful reasoning hop — the constant was previously a leaf, so any path from it to the target was non-trivial; now that path has been extended by one hop.

Why layer-wise prevents reasoning shortcuts: The strategy expands leaf constants systematically, layer by layer. A shortcut would require adding a triplet that connects a new constant directly to a variable close to the target — but the layer-wise strategy only adds triplets that connect through the variable that replaced the constant, maintaining the distance from the target.

The number of expanding layers $l$ is described as a hyperparameter controlling "task coverage and difficulty." Larger $l$ yields deeper graphs (more hops between any leaf constant and the target), producing more complex questions. The paper doesn't specify what values of $l$ were used in the final dataset, but the tool call analysis (Figure 8c) shows final trajectories requiring up to 30 tool calls, suggesting deep expansion.

Formal expression of an expansion step:

$q^{n+1}(T) = \text{Expander}(C, q^n(T))$

The Expander takes a leaf constant $C$ from the current formal question $q^n(T)$ and returns a new formal question $q^{n+1}(T)$ where $C$ has been "pushed down" — replaced by a variable whose value depends on solving a sub-query.

Why this strategy is enabled by formalization: The graph structure (which constants are leaves, which layer they're in) is only visible because the question has been formalized as a list of triplets. Without formalization, you cannot algorithmically identify leaf constants or verify that expansion preserved the answer set — you'd be expanding in natural language, hoping the result is still coherent.

Expander Agent (Section 3.2.3)

The Expander is the workhorse of the expansion process — an LLM-based agent that, given a leaf constant $C$ and the current formal question $q^n(T)$, autonomously:

1. Searches the web for information about $C$.
2. Synthesizes a sub-question whose answer is $C$.
3. Validates the sub-question against the formalization.
4. Merges the sub-question's formal representation with $q^n(T)$ to produce $q^{n+1}(T)$.

The Expander is built on the ReAct framework (Yao et al., 2023), which interleaves reasoning (Thought), tool use (Action), and environmental feedback (Observation) in a loop.

ReAct execution loop: At each time step $t$, the agent produces:

• $\tau_t$ (Thought) — free-form natural language reasoning about what to do next, what information is needed, and how to interpret previous observations.
• $\alpha_t$ (Action) — a structured call to one of the available tools, with parameters.
• $o_t$ (Observation) — the result returned by the environment in response to the action.

The loop continues until the agent emits a special answer action to finalize the sub-question.

Each Action $\alpha$ decomposes into $(\tau, \phi)$, where $\tau$ specifies the action type (which tool to use) and $\phi$ contains the tool-specific parameters.

Tools available to the Expander:

1. Search: Executes a Google search for several queries about the constant $c$. The parameters are $\phi = \{\text{queries of } c, \text{filter\_year}\}$. The filter_year parameter enables temporal filtering of search results — important for time-sensitive constants (e.g., searching for a sports team's roster in a specific year).

   Observation returned: Top relevant URLs and their text snippets.

   Why multiple queries: A single search query may not surface all relevant aspects of $C$. For instance, if $C$ is "Berliner FC Dynamo," the Expander might search for the team's founding year, its league history, and its notable players in separate queries, obtaining complementary information.

2. Summarize: Visits multiple URLs retrieved by Search and summarizes their content. This action is explicitly identified as the key to implementing R-Union (Section 3.2.3).

   The parameters are $\phi = \{\text{urls}, \text{goal}\}$. The goal specifies what aspect of the constant the Expander is trying to learn — this focuses the summarization model on relevant content.

   Observation returned: A summarization of knowledge about $c$ from the given URLs, produced by a separate summarization model (Qwen-2.5-72B in the paper's implementation).

   How this implements R-Union: Recall that R-Union $R(S_1) \cup R(S_2) \cup \dots$ requires collecting entities from multiple source sets. The Summarize tool achieves this by aggregating information across multiple web pages — each page may contribute part of the union set. For instance, to determine "players who played for Berliner FC Dynamo in 2004 or 2005," the Expander might visit the team's 2004 roster page, its 2005 roster page, and a summary page covering both seasons, then summarize them into a single merged answer. The summarization output is a union of the information from the visited URLs.

   Why a separate LLM for summarization: Full web page content is too long to fit in the Expander's context window. Summarization compresses the relevant information, enabling the Expander to reason about the accumulated knowledge without being overwhelmed by raw HTML.

3. Validate: After the Expander has collected sufficient information and formulated a candidate sub-question, it uses this tool to check the sub-question's validity. The validation performs two checks:

   • Structural consistency check: An LLM (QwQ) is called to verify whether the type of $C$ satisfies the sub-question's constraints, based on the formalization. The paper specifies: "we don't check whether $C$ is strictly the answer to the sub-question. Instead, it checks if the type of $C$ satisfies the sub-question." This is a weaker but more pragmatic check — verifying strict equality would require exhaustively confirming no other entity also satisfies the constraints, which is infeasible. Verifying type consistency (e.g., "$C$ is a football team, and the sub-question asks for a football team") catches gross mismatches without requiring complete knowledge.

   • Non-triviality check: QwQ is asked to answer the sub-question directly (without web search). If QwQ can correctly predict that the answer is $C$ using only its parametric knowledge, the sub-question is considered invalid — it's too easy, because an LLM could answer it without the web search capability the agent is supposed to learn. This check ensures that the training data genuinely requires information-seeking behavior, not just recall of facts the base model already knows.

   Observation returned: Detailed validation results. If either check fails, the Expander must revise the sub-question or collect more information.

   Why these specific checks: The structural consistency check prevents the Expander from generating sub-questions that are syntactically valid in the formalization but semantically nonsensical (e.g., "which year plays in Berliner FC Dynamo?" — a type mismatch). The non-triviality check prevents the training data from being dominated by questions whose answers are already known to the base model — such questions wouldn't teach information-seeking skills.

Termination: The expansion loop terminates when the Expander emits the answer action, which finalizes the sub-question construction. At this point, the Expander outputs a verified formal sub-question (a list of triplets) for which $C$ is the answer, along with the natural language rendering of that sub-question.

Merging with the main question: The Expander replaces the constant $C$ in $q^n(T)$'s triplet list with the new variable and prepends the sub-question's triplets, yielding $q^{n+1}(T)$.

Why the Expander is agentic rather than scripted: The web is unstructured — there's no API that takes a constant and returns a list of KPs that could define it. The Expander must creatively explore search results, identify which aspects of the constant are interesting (which relations it participates in), formulate search queries, decide which pages to visit, and synthesize disparate information fragments into a coherent sub-question. This requires the flexibility and open-ended reasoning that only an LLM-based agent provides. The formalization provides the target structure (what a valid sub-question looks like), but the Expander provides the means of discovering that structure in the wild.

Trajectory Construction and Filtering (Section 3.3)

After expansion, the pipeline has a collection of complex, formalization-verified questions. The next stage converts these into agent trajectories — sequences of thought-action-observation steps that solve the question — which become the supervised training data.

Agent setup for trajectory collection:

A separate ReAct agent is instantiated, structurally similar to the Expander but with different tools:

• Search: Same as Expander — Google search with multiple queries, returning top-10 results per query (titles, snippets, URLs).
• Visit: Retrieves the full content of specific web pages. Content is fetched using Jina (Jina.ai, 2025), then summarized by Qwen-2.5-72B to extract information relevant to the agent's current goal. This two-tool setup (search for discovery, visit for deep extraction) mirrors the standard web agent toolset used in WebDancer (Wu et al., 2025a) and other frameworks.

Rollout procedure: For each question, the agent runs 5 independent rollouts — 5 separate trajectories starting from the same question but with different agent decisions (which queries to issue, which pages to visit, what reasoning to pursue).

Purpose of multiple rollouts: Multiple rollouts provide (a) diversity in the trajectories for training (the model sees different valid ways to solve the same question), and (b) a signal for filtering: a question is considered solvable if at least one rollout succeeds.

Filtering strategies:

1. Correctness filtering: An LLM judge evaluates the final answer of each trajectory. Only trajectories whose final answer matches the ground-truth answer (as defined in the formalized question) are retained. Trajectories with tool call errors (malformed actions, failed searches) are also removed.
2. Quality filtering: Trajectories are removed if they contain:
   • Hallucinations of observation: The model generates content that it claims came from a tool, but that wasn't actually returned. This is a common failure mode in agent trajectories where the LLM "makes up" what it thinks a web page should contain.
   • Severe repetitions: The agent gets stuck in a loop, repeating the same search queries or visiting the same pages without making progress.

Final dataset size: After filtering, 5,000 trajectories are retained. This is a significant reduction from the initial seed questions (18,000 seed questions, each expanded through multiple layers, each with 5 rollouts). The paper doesn't provide a detailed breakdown of how many trajectories are filtered at each stage, but the 5,000 final count reflects the stringency of the quality criteria — most rollouts fail either in correctness or in quality.

Why 5,000 trajectories? This is a moderately sized SFT dataset for agent training (for comparison, WebDancer's E2HQA and MHQA datasets are in a similar range). The filtering is aggressive to ensure high data quality — training on noisy trajectories would teach the model incorrect behaviors, which RL would then amplify. The paper implicitly prioritizes precision (fewer but correct trajectories) over recall (maximizing data volume), consistent with the finding that SFT data quality is the foundation for the entire training pipeline.

Agent Training (Section 3.4)

The final stage trains the information-seeking agent model using the collected trajectories, following the standard SFT → RL pipeline.

Supervised Fine-Tuning (SFT):

Given a trajectory as a sequence of tokens:

$\mathcal{T} = (\tau_1, a_1, o_1, \dots, \tau_n, a_n, o_n)$

where $\tau_i$ are thought tokens, $a_i$ are action tokens (tool calls), and $o_i$ are observation tokens (tool responses), the SFT loss is:

$L = -\frac{1}{\sum_{i=1}^{|\mathcal{T}|} \mathbb{I}[x_i \in o]} \sum_{i=1}^{|\mathcal{T}|} \mathbb{I}[x_i \in o] \cdot \log \pi_{\theta}(x_i | x_{<i})$

where $\pi_{\theta}$ is the model being trained, $|\mathcal{T}|$ is the total number of tokens in the trajectory, and $\mathbb{I}[x_i \in o]$ is an indicator function that is 1 if token $x_i$ belongs to an observation segment and 0 otherwise.

What it computes: Standard next-token prediction loss, but with the loss masked out (ignored) for all tokens that are not part of an observation. The numerator sums the negative log-probabilities over observation tokens only; the denominator normalizes by the total number of observation tokens. During training, the model learns to predict what the environment should return in response to its actions, but is not penalized for its predictions of its own thoughts and actions.

Why mask out non-observation tokens: In a ReAct trajectory, thoughts and actions are generated by the agent — they represent decisions the agent makes. Learning to predict your own thoughts from an expert trajectory is behavioral cloning: you're training the model to replicate the exact sequence of decisions the expert made. However, for tool-use tasks, the critical skill is interpreting observations and deciding what to do next based on them. Masking out the loss on thoughts and actions means the model only receives gradient signal for understanding what the environment returned and what that implies — it's not forced to copy the expert's exact query phrasing or reasoning word choice. This should lead to more robust generalization: the model learns the mapping from observations to correct continuations, rather than memorizing specific thought-action sequences.

The practical effect is that during SFT, the model sees the full trajectory as context (so it learns the structure of agent behavior), but is only trained to predict the observation tokens — the parts of the trajectory that come from the external environment, not from its own policy.

SFT hyperparameters: Batch size 32, learning rate $5\times 10^{-6}$, warmup plus cosine decay schedule, weight decay 0.1 (Appendix B.1).

Reinforcement Learning (RL) with GRPO:

After SFT, the model is further optimized using Group Relative Policy Optimization (GRPO) (Shao et al., 2024). GRPO is an RL algorithm designed for language model fine-tuning that uses group-relative advantages rather than requiring a separate value function (critic).

The GRPO objective is:

$\begin{aligned} \mathcal{J}_{\text{GRPO}}(\theta) &= \mathbb{E}_{(q,a) \sim \mathcal{D}, \{y_i\}_{i=1}^G \sim \pi_{\theta_{\text{old}}}(\cdot | \text{context})} \\ &\quad \left[ \frac{1}{\sum_{i=1}^G |y_i|} \sum_{i=1}^G \sum_{t=1}^{|y_i|} \min \left( r_{i,t}(\theta) \hat{A}_{i,t}, \text{clip} \left( r_{i,t}(\theta), 1 - \varepsilon_{\text{low}}, 1 + \varepsilon_{\text{high}} \right) \hat{A}_{i,t} \right) \right] \end{aligned}$

where:

• $\mathcal{D}$ is the dataset of question-answer pairs $(q, a)$.

• $G$ is the number of rollouts sampled per question (set to 8, per Appendix B.2).

• $y_i$ is the $i$-th rollout — a complete trajectory generated by the old policy $\pi_{\theta_{\text{old}}}$.

• $|y_i|$ is the length (in tokens) of rollout $i$.

• $r_{i,t}(\theta) = \frac{\pi_{\theta}(o_i | q_i, o_{i,<t})}{\pi_{\theta_{\text{old}}}(o_i | q_i, o_{i,<t})}$ is the importance sampling ratio at timestep $t$ of rollout $i$: the ratio of the probability the new policy assigns to token $o_i$ versus the probability the old policy assigned to it, given the question and preceding tokens.

• $\hat{A}_{i,t} = \frac{R_i - \text{mean}(\{R_i\}_{i=1}^G)}{\text{std}(\{R_i\}_{i=1}^G)}$ is the group-relative advantage at timestep $t$ of rollout $i$: the rollout's total reward $R_i$, normalized by the mean and standard deviation of rewards across the $G$ rollouts in the same group.

• $\varepsilon_{\text{low}}$ and $\varepsilon_{\text{high}}$ are clipping parameters that bound how much the importance sampling ratio can deviate from 1, preventing overly large policy updates. The paper does not specify the exact clipping values, but they are standard in PPO/GRPO implementations (typical: $\varepsilon_{\text{low}} = 0.8$, $\varepsilon_{\text{high}} = 1.2$ for a clip around 1.0).

• $R_i$ is the total reward for rollout $i$. The paper does not explicitly define the reward function, but given the GRPO context and the task (reaching the correct answer), $R_i$ is likely a binary or sparse reward: +1 if the final answer matches the ground truth, 0 otherwise. The group-relative normalization means that if most rollouts in a group succeed, the advantage for successful rollouts is small (they're not much better than average), but if most fail, the successful ones receive a large positive advantage — the policy is strongly encouraged toward behaviors that worked when others didn't.

What it computes: For each question, the old policy generates $G$ rollouts. Each rollout receives a total reward based on whether it found the correct answer. The advantage of each rollout is computed by normalizing rewards within the group. Then, for each token in each rollout, the policy update pushes the new policy toward actions that had positive advantage (good rollouts) and away from actions that had negative advantage (bad rollouts), weighted by the importance sampling ratio and clipped to prevent instability.

The outer expectation $\mathbb{E}_{(q,a) \sim \mathcal{D}}$ means this update is computed over a batch of questions from the training set — the paper reports micro-batch size 32 and total batch size 128 (Appendix B.2).

Why GRPO over standard PPO: GRPO eliminates the need for a learned value function (critic) by using the empirical mean and standard deviation of rewards within each group as a baseline. This is computationally simpler (no separate critic model to train) and is particularly well-suited to tasks with sparse binary rewards, where value function learning is challenging. The group-relative baseline is unbiased in expectation (the expected reward of a random rollout is the group mean) and adapts automatically to question difficulty — a reward of 0 on an easy question (where other rollouts succeeded) is penalized more heavily than a reward of 0 on a hard question (where everyone failed).

RL hyperparameters (Appendix B.2): Temperature 1.0, $top_p = 1.0$ (no top-p filtering), batch size 128, mini-batch size 32, learning rate $1\times 10^{-6}$, 8 rollouts per group (G=8). The high temperature (1.0) with no top-p truncation means the agent explores broadly during RL, sampling diverse trajectories to discover strategies that succeed.

Why SFT then RL: The SFT phase provides a reasonable initial policy that can complete the task some fraction of the time — without this, RL would receive almost no positive reward signal (the agent would never stumble upon the correct answer by random exploration) and would learn nothing. The RL phase then optimizes the policy to maximize the probability of those successful trajectories, "activating advanced information-seeking capabilities" (Section 4.3.3) — essentially, amplifying and refining the behaviors that SFT demonstrated were possible.

Summary of Design Choices and Their Justifications:

• Set-theoretic formalization over natural language prompting for question structure: Enables mechanical validation, controllable complexity, and systematic exploration of the task space. Without it, structural errors (redundancy, shortcuts) are undetectable during synthesis.
• KP Representation as flat triplets over nested expressions: Optimized for LLM autoregressive generation — flat lists are more reliably produced than nested parenthesized expressions.
• Distributive law for R-Union: Collapses union operations into source sets, reducing the representation to intersection of heterogeneous relations only — fewer operation types for the Expander to handle.
• Layer-wise expansion over random or sequential: Prevents redundancy (constants connected to constants) and reasoning shortcuts (direct paths to target), ensuring every added triplet increases genuine reasoning depth.
• Agentic Expander over scripted web scraping: The web is unstructured; creative exploration and synthesis require LLM-level reasoning. Scripted approaches would break on the diversity of entity types and page structures.
• Two-stage validation (type consistency + non-triviality): Catches both semantic errors (wrong entity type) and difficulty failures (question answerable without search) without requiring exhaustive correctness verification.
• Loss masking on non-observation tokens during SFT: Encourages learning the mapping from observations to actions rather than memorizing specific thought-action sequences.
• GRPO over PPO for RL: Eliminates critic model training overhead, natural fit for sparse binary rewards, group-relative advantages adapt to question difficulty automatically.

4. Key Insights and Innovations

Innovation 1: Formalization-Driven Synthesis Inverts the Data Generation Pipeline, Making Task Structure Prescriptive Rather Than Emergent

The dominant paradigm in information-seeking (IS) data synthesis — represented by WebWalkerQA, WebDancer's CRAWLQA, and WebSailor's SailorFog-QA — treats the synthesis problem as information-first: collect web content, organize it into some structural format (chains, graphs, coreference networks), and then prompt an LLM to generate questions that fit the collected content. This workflow makes the reasoning structure of the resulting question an emergent property of whatever information happened to be collected. The paper's central intellectual move is to invert this entirely: formalize the desired reasoning structure first using set-theoretic constructs, then use that formalization to drive what information to collect, how to compose it, and how to validate the result.

This is not merely a reordering of steps. It shifts the synthesis problem from reactive (what questions can I extract from this pile of web pages?) to prescriptive (what reasoning graph do I want to construct, and what web facts do I need to instantiate it?). The analogy to formal theorem proving (Section 5.2) is apt but incomplete: in Lean 4, the formal language is a target (you translate natural language problems into it for verification). In WebShaper, the formal language is a generative skeleton — it specifies what to build before anything is built. This is closer to how a compiler uses an intermediate representation to guide code generation than to how a proof assistant verifies completed proofs.

The empirical significance of this inversion is not just that WebShaper outperforms information-driven datasets (Table 2: WebShaper-trained models achieve 43.6–53.3 on GAIA across backbones, versus 32.0–45.6 for the best information-driven alternative). The deeper point is that the formalization enables capabilities that are structurally impossible in the information-driven paradigm:

• Controllable complexity: The number of expansion layers l is a direct, interpretable hyperparameter controlling reasoning depth. In information-driven approaches, complexity is whatever the LLM happened to produce — you can filter for harder questions post-hoc, but you cannot specify a desired complexity profile and synthesize to match it.
• Mechanical validation: The Validate tool's checks (type consistency, non-triviality) operate on the formal representation. No equivalent validation is possible when the question exists only in natural language — you can ask an LLM "is this question answerable?" but the LLM's answer is itself unreliable, as the filtering difficulties in seed construction demonstrate (Section 3.1).
• Systematic coverage: The formalization defines a space of possible reasoning structures via KP composition. Layer-wise expansion systematically explores this space by traversing leaf constants. Information-driven approaches explore whatever subspace of structures happens to emerge from web crawls — a convenience sample, not a systematic coverage.

The paper positions this as the first formalization of information-seeking tasks in set theory (Section 1: "To the best of our knowledge, we are the first to derive it based on set theory"). Whether or not that claim of primacy holds, the substantive contribution is demonstrating that formalization is not just academically elegant — it is practically enabling for data synthesis at scale. The ablation in Figure 7a confirms this: the formalization-driven variant ("FL") consistently outperforms a natural-language-driven variant ("NL") across all backbones. The gap is not attributable to better prompts or more compute — it comes from the structural guarantees that only a formal representation can provide.

Innovation 2: Layer-Wise Expansion as a Structural Cure for Redundancy and Reasoning Shortcuts

Prior data synthesis methods, when viewed through the lens of the KP graph representation (Figure 4), produce question structures that fall into two categories: random (adding constraints to arbitrary nodes, producing constants connected to constants — redundancy that adds bulk without reasoning depth) and sequential (extending a single reasoning chain, risking shortcuts where a new constraint directly connects a constant to the target, bypassing intermediate hops). These are not random failures — they are systematic consequences of expanding questions without a structural discipline. When you expand a natural language question by prompting an LLM to "make it more complex," the LLM has no representation of the reasoning graph and no way to check whether its additions deepen the graph or merely decorate it.

The layer-wise expansion strategy (Section 3.2.2, Figure 4c) is the paper's algorithmic answer to this structural problem. By identifying leaf constants through graph traversal and expanding them layer by layer, the strategy guarantees two properties that random and sequential expansion cannot:

1. No redundancy: Every added triplet connects a new constant to a variable that was previously a leaf, extending every path from that variable to the target by exactly one hop. Constants never connect directly to other constants.
2. No reasoning shortcuts: The expansion always pushes constants further from the target — it increases the minimum hop distance between any leaf and the target, never decreases it. A shortcut would require adding a triplet that bypasses existing variables, which the layer-wise traversal structurally prevents.

This is significant beyond the performance gain (Figure 7b shows layer-wise outperforming sequential expansion across all backbones). It demonstrates that the structure of expansion matters independently of the formalization — even with formal representations, a sequential expansion strategy can introduce shortcuts that undermine the intended reasoning complexity. The field's default assumption has been that if you have a good question generator and a good verifier, the expansion order doesn't matter much — you'll filter out bad questions post-hoc. WebShaper shows that post-hoc filtering cannot compensate for structural guarantees built into the generation process itself: a shortcut-containing question might pass correctness filters (the answer is still correct) and even non-triviality checks (an LLM can't guess the answer without search), yet fail to teach the multi-hop reasoning it was designed for because the model learns to exploit the shortcut rather than traverse the full graph.

The tool call analysis (Figure 8) provides behavioral evidence for this claim. WebShaper-trained agents execute significantly more search operations, visit more pages, and sustain longer tool-call sequences than agents trained on information-driven datasets. This is not because WebShaper questions are harder in some abstract sense — it's because they are structurally deeper: there is no shortcut to exploit, so the agent must genuinely traverse the reasoning graph to succeed.

This insight has implications beyond information-seeking. Any domain where training data is synthesized by iteratively composing simpler structures — program synthesis, multi-step planning, hierarchical reasoning — faces the same risk: naive composition can introduce unintended short paths that allow models to succeed without learning the intended compositional reasoning. Layer-wise (or more generally, structure-preserving) expansion is a general design principle, not a WebShaper-specific trick.

Innovation 3: The Expander Agent Operates as a Synthesis-Time Analog of the Target Agent, Creating a Closed-Loop Data Generation System

The Expander (Section 3.2.3) is not merely a question-generation module — it is an agent that performs information-seeking in order to create information-seeking tasks. It searches the web, visits pages, summarizes content, and synthesizes sub-questions using the same ReAct framework and similar tools (Search, visit-equivalent summarization) as the target agent it is training data for. This creates a closed-loop system: the synthesis process itself exercises the capabilities that the synthesized data is designed to teach.

This is a distinctive architectural choice compared to prior synthesis approaches. In WebDancer's CRAWLQA, question expansion is done by an LLM prompted with the existing question and retrieved content — a single inference call, not an agent loop. In WebWalkerQA, questions are generated from pre-collected webpage content — no dynamic web interaction during synthesis. The Expander, by contrast, is an active participant in the web environment during synthesis, making decisions about what to search for, which pages to visit, and how to compose retrieved facts into a formal sub-question.

The implications of this closed-loop design are subtle but important:

• Distributional alignment: The Expander's search behavior during synthesis produces questions whose difficulty and structure reflect what is actually findable on the web through search and visit operations. If a particular entity has sparse or poorly structured web presence, the Expander will struggle to construct a valid sub-question about it — and that question won't enter the training set. The resulting dataset is implicitly filtered for "answerability given realistic web access patterns," which is exactly the condition the target agent will face. In contrast, information-driven approaches can generate questions from pre-collected content that is not practically retrievable through search — creating a distributional mismatch between training and deployment.

• Scalability through self-play: The Expander generates questions that are at the frontier of its own capability. As the Expander model improves (or as better base LLMs become available), it can generate harder questions, which in turn train better target agents. This is a self-play dynamic analogous to how AlphaGo generated training data by playing against itself — the synthesis system and the target system co-evolve. The paper doesn't explore this iterative refinement explicitly, but the architecture supports it: the same QwQ model serves as the base for both the Expander and the target agent, creating a natural path for mutual improvement.

• Validation through behavioral consistency: The Validate tool's non-triviality check (can an LLM answer this without search?) implements a form of behavioral validation: it tests whether the sub-question actually requires web interaction by having a model attempt it without web access. This is a more meaningful validity criterion than static checks (grammar, answer format) because it directly tests the behavioral property the training data is supposed to impart — the necessity of information-seeking. A question that passes static checks but fails behavioral validation would teach the model nothing about web search; flagging it during synthesis prevents wasted training.

The Expander is thus not just a means to an end (generating questions) — it is a design pattern for synthesis-time quality assurance through agentic simulation. The synthesis agent mimics the target agent's information-gathering process, and in doing so, implicitly verifies that the generated tasks are both solvable and non-trivial under realistic conditions. This pattern could generalize to other domains where training data requires multi-step environmental interaction to verify.

Innovation 4: The Formalization Enables Difficulty- and Structure-Aware Data Synthesis Without Human Annotation of Reasoning Complexity

A persistent challenge in training data synthesis is calibrating difficulty. If your dataset contains a random mix of trivial and impossible questions, the model learns a random mix of superficial and frustrated behaviors. Prior IS datasets addressed this implicitly — WebWalkerQA's multi-source questions are harder than its single-source questions, and WebDancer's expansion process produces more complex questions than its seeds — but the difficulty gradient is an emergent property, not a designed one. You cannot look at a WebDancer question and say "this requires exactly three intersection operations" because the reasoning structure is implicit in the natural language.

WebShaper's formalization makes the reasoning structure explicit and countable. The number of triplets in the KP representation, the depth of the variable dependency graph, the number of R-Union operations (captured in merged constant sets) — these are all directly measurable structural features that correlate with reasoning complexity. The layer-wise expansion hyperparameter l provides a direct knob for controlling overall depth. This means WebShaper can, in principle, generate datasets with specified difficulty profiles — 20% single-intersection questions, 50% double-intersection, 30% triple-intersection with recursive sub-queries — by controlling how many expansion layers are applied and to which constants.

The paper does not fully exploit this capability (it reports a single dataset, not a difficulty-stratified ablation), but the architecture supports it. This is significant because it opens the door to curriculum learning for information-seeking agents: train first on shallow questions (few triplets, no recursion), then on deeper ones, progressively increasing the reasoning graph complexity. The field currently lacks the vocabulary to even describe such a curriculum — WebShaper provides it.

Contrast this with the dominant approach to difficulty calibration in LLM training data: rely on model-based difficulty estimates (a larger model's loss on each example) or heuristic proxies (question length, number of entities mentioned). These are correlational, not causal — a long question might be long because it's verbose, not because it requires deep reasoning. The KP graph depth is a causal measure of reasoning complexity: each additional layer requires the agent to resolve one more intermediate entity before it can reach the answer. This causal link between formal structure and behavioral difficulty is what gives the formalization its power as a difficulty calibration tool.

The practical payoff is visible in the RL results (Figure 6). The RL phase amplifies GAIA performance by +7.8 points for the 32B model and +13.5 points for the 72B model. The paper attributes this to the "breadth and complexity of tasks introduced by our task formalization" stimulating diverse IS strategies during RL. If the SFT dataset contained a flat difficulty distribution, RL would optimize within a narrow behavioral neighborhood. The formalization enables a wide range of reasoning depths, giving RL a rich landscape of behaviors to explore and amplify. The +13.5 point gain on the 72B model is substantial — it represents the model learning strategies that were present in the SFT data distribution but not yet reliably executed, and RL making them robust. A less structurally diverse SFT dataset would give RL less to work with.

5. Experimental Analysis

Evaluation Methodology

• Dataset. The paper evaluates on two benchmarks: GAIA (Mialon et al., 2023) — a test set of 165 questions designed for general AI assistants, divided into three difficulty levels (Level 1 easiest, Level 3 hardest) — and WebWalkerQA (Wu et al., 2025b) — a benchmark requiring multi-source web navigation, divided into Easy, Medium, and Hard subsets. GAIA is the primary benchmark in the deep research community, used by OpenAI Deep Research and other proprietary systems. Both benchmarks use the LLM-as-Judge paradigm for answer grading (Li et al., 2025c), where an LLM compares the agent's final answer to the ground truth and determines correctness.

• Base model(s). Three backbone models are used: Qwen-2.5-32B, Qwen-2.5-72B (Yang et al., 2024), and QwQ-32B (Team, 2025). The paper does not explicitly justify why these specific models were chosen beyond their being representative of current open-source capabilities. QwQ-32B is notable as a reasoning-enhanced model, making it a stronger base for information-seeking tasks. For the summarization component of the Expander and trajectory construction agents, Qwen-2.5-72B is used as a separate tool. The seed question filtering uses the WebDancer framework running QwQ (Section 3.1). The Expander agent is also based on QwQ (implied by the structural alignment mentioned in Section 3.3: "instantiate an agent framework based on QwQ structurally aligned with the Expander").

• Metrics. The primary metric is Pass@1 — the fraction of questions for which the agent's single generated answer matches the ground truth (as judged by an LLM evaluator). This is the standard metric in the GAIA benchmark and agent evaluation literature. Results are reported per difficulty level and as an overall average.

• Baselines. The paper compares against multiple categories of methods:

  No-agency baselines (direct LLM prompting without web search tools):

  • Base: The backbone model prompted directly to answer the question without any tool access.
  • RAG: Retrieval-Augmented Generation, where the model receives retrieved documents as context but does not actively search or navigate.

  Closed-source agentic frameworks:

  • OpenAI DR: OpenAI's proprietary Deep Research system (OpenAI, 2025), representing the upper bound of current capabilities.

  Open-source agentic frameworks:

  • Search-o1 (Li et al., 2025b): An agentic search-enhanced reasoning framework.
  • WebDancer (Wu et al., 2025a): A prior state-of-the-art IS agent that uses a different data synthesis approach (E2HQA dataset).
  • WebThinker-Base and WebThinker-RL (Li et al., 2025c): A deep research agent available in both SFT-only and RL-enhanced versions.
  • Simple DS (SimpleDeepResearch; Sun et al., 2025): Another deep research agent (GAIA-only results reported).

  For the data comparison experiments (Table 2), additional training datasets are compared:

  • WebWalkerQA dataset (Wu et al., 2025b): Generated from random walks over interlinked URLs.
  • E2HQA (Wu et al., 2025a): WebDancer's dataset where simple questions are rewritten into complex ones.
  • MHQA: A composite dataset integrating existing single-hop and multi-hop QA datasets, with majority human annotation.

• Generation budget / compute accounting. The paper does not specify a fixed inference compute budget for evaluation. Unlike the reference example, which carefully accounts for FLOPs and generation counts, WebShaper reports only the final accuracy at whatever cost the agent incurred during its rollouts. The trajectories are generated using a ReAct agent with Search and Visit tools (Appendix A), performing up to 30+ tool calls per question (Figure 8c), but the number of rollouts used at evaluation time is not explicitly stated. Given the Pass@1 metric and the 5000 SFT trajectory dataset, the evaluation likely uses a single rollout per question. The lack of compute accounting makes it difficult to compare efficiency — we know WebShaper achieves higher accuracy than baselines, but not whether it uses more or less inference compute to do so.

• Cross-validation / statistical protocol. None reported. The paper does not describe any cross-validation procedure, statistical significance testing, or confidence intervals for the reported results. The GAIA test set contains 165 questions (split across three difficulty levels, with Level 3 having only ~12 questions based on the ~8.3% resolution granularity visible in Table 1). The WebWalkerQA test set size is not specified. With such small evaluation sets, individual question outcomes have large impacts on percentages — a single question on GAIA Level 3 represents approximately 8.3 percentage points. Statistical claims about relative performance should be interpreted cautiously given the absence of variance estimates.

Main Quantitative Results

Overall Performance on GAIA and WebWalkerQA

Table 1 presents the primary results. The headline numbers are:

• WebShaper on Qwen-2.5-72B achieves 60.1% average on GAIA, making it "currently the only open source method with a score of more than 60 points" (Section 4.2). This outperforms the next best open-source method (WebSailor, not in Table 1 but mentioned in text) by 4.7 points, and the best Table 1 competitor (WebDancer on QwQ-32B at 51.5%) by 8.6 points.

• On WebWalkerQA, WebShaper on Qwen-2.5-72B achieves 52.2% average, the highest among all methods. The next best is WebShaper on Qwen-2.5-32B at 51.4%.

• The best-performing variant uses Qwen-2.5-72B, not the reasoning-enhanced QwQ-32B. WebShaper on QwQ-32B achieves 53.3% on GAIA and 49.7% on WebWalkerQA — substantially lower than the 72B model despite QwQ's stronger reasoning capabilities. This suggests that general capacity (72B scale) contributes more to web agent performance than specialized reasoning training, at least for WebShaper's synthesis approach.

Scaling behavior across backbones: For WebShaper specifically, we observe a consistent pattern:

• Qwen-2.5-32B → 72B: GAIA improves from 52.4 to 60.1 (+7.7 points); WebWalkerQA from 51.4 to 52.2 (+0.8).
• Qwen-2.5-32B → QwQ-32B (same parameter count, different training): GAIA improves from 52.4 to 53.3 (+0.9 points) — a marginal gain. On WebWalkerQA, performance actually decreases from 51.4 to 49.7.

This suggests something important about the interaction between model architecture and the WebShaper dataset: the dataset benefits more from raw model scale (32B → 72B) than from reasoning-oriented training (Qwen-2.5-32B → QwQ-32B), especially on GAIA.

Comparison with proprietary systems: OpenAI Deep Research achieves 67.4% on GAIA — 7.3 points above WebShaper's best (60.1%). The WebShaper authors frame this as "close to the SOTA OpenAI DR system" (Section 4.2). Whether a 7.3 point gap on a 165-question test constitutes "close" is debatable, particularly since Level 3 difficulty (where the gap is largest: 47.6% for OpenAI vs. 16.6% for WebShaper) may represent the most practically important regime.

Difficulty-level analysis: On GAIA, performance predictably degrades with difficulty for all methods:

• Level 1: WebShaper-72B reaches 69.2%, competitive with OpenAI DR's 74.3%.
• Level 2: WebShaper-72B achieves 63.4%, compared to OpenAI DR's 69.1%.
• Level 3: WebShaper-72B drops to 16.6% (all three WebShaper backbones achieve the same 16.6% on Level 3 — Qwen-2.5-32B, QwQ-32B, and Qwen-2.5-72B all score identically here). This is substantially below OpenAI DR's 47.6%. The fact that all three backbones plateau at the same 16.6% suggests a data-coverage limitation rather than a model-capacity limitation — the WebShaper dataset may simply not contain training examples at the complexity level required for GAIA Level 3 questions.

This pattern — strong performance on easier levels, sharp degradation on the hardest — mirrors the difficulty-dependent scaling behavior observed in the reference example's analysis of test-time compute, though the underlying mechanism is different.

Data Comparison: WebShaper vs. Alternative Training Datasets

Table 2 provides the cleanest evidence for WebShaper's data quality advantage, since it controls for model architecture and training procedure, varying only the SFT dataset.

On Qwen-2.5-32B:

• WebShaper: 43.6% average
• E2HQA (WebDancer's dataset): 39.8%
• MHQA (human-annotated composite): 35.9%
• WebWalkerQA: 32.0%
• WebShaper's advantage over the second-best (E2HQA): +3.8 points.

On Qwen-2.5-72B:

• WebShaper: 45.6%
• E2HQA: 44.6%
• MHQA: 43.6%
• WebWalkerQA: 38.8%
• WebShaper's advantage narrows to just +1.0 point over E2HQA. Interestingly, E2HQA shows a dramatic Level 3 improvement for the 72B model (16.6% vs. 0.0% for most other dataset-model combinations at this level).

On QwQ-32B:

• WebShaper: 53.3%
• E2HQA: 45.6%
• WebWalkerQA: 45.6%
• MHQA: 41.7%
• WebShaper's advantage widens substantially to +7.7 points over the tied second-place datasets.

Key pattern: WebShaper's advantage over alternative datasets is not uniform across backbones. It is largest on QwQ-32B (+7.7), moderate on Qwen-2.5-32B (+3.8), and marginal on Qwen-2.5-72B (+1.0). This suggests that the WebShaper dataset's structural properties (formalization-guided reasoning, deeper multi-hop structure) are most beneficial when combined with a reasoning-specialized model like QwQ — the dataset's structural depth complements the model's reasoning capabilities. On the largest general-purpose model (72B), the dataset advantage narrows, possibly because the 72B model's greater capacity allows it to extract useful patterns even from structurally inferior data.

Comparison with human-annotated data: MHQA, which includes human-annotated questions, consistently underperforms WebShaper (35.9 vs. 43.6 on 32B; 43.6 vs. 45.6 on 72B; 41.7 vs. 53.3 on QwQ). This is notable because it suggests that synthetic data generated through formalization-driven synthesis can outperform human-curated datasets for this task, likely because the formalization enables systematic coverage of reasoning structures that human annotators might not naturally produce.

Effect of Reinforcement Learning

Figure 6 shows the performance difference between SFT-only and SFT+RL training on the WebShaper dataset.

On GAIA (Figure 6a):

• Qwen-2.5-32B: SFT achieves ~44.6%, RL adds +7.8 points to reach ~52.4%.
• Qwen-2.5-72B: SFT achieves ~46.6% (extrapolating from Table 2: 45.6% is SFT-only), RL adds +13.5 points to reach ~60.1%.

On WebWalkerQA (Figure 6b):

• Qwen-2.5-32B: SFT achieves ~43.6%, RL adds +7.8 points to reach ~51.4%.
• Qwen-2.5-72B: SFT achieves ~38.7%, RL adds +13.5 points to reach ~52.2%.

Interpretation: The RL gains are substantial and scale with model size — the 72B model benefits nearly twice as much from RL as the 32B model (+13.5 vs. +7.8 points on both benchmarks). This is consistent with the "RL stimulation" narrative in Section 4.3.3: the larger model has more capacity to learn sophisticated search strategies from the reward signal, while the smaller model's behavioral repertoire is more constrained.

An important caveat: the Figure 6 bars appear to show final performance after RL, with the SFT baseline being the starting point. However, the SFT numbers in Figure 6 for Qwen-2.5-72B (~46.6% GAIA, ~38.7% WebWalkerQA) differ from the SFT numbers in Table 2 for WebShaper on Qwen-2.5-72B (45.6% GAIA). The discrepancy is small (1 point on GAIA) but unexplained — it could reflect different evaluation conditions, different checkpoints, or simple rounding in the figure.

Tool Call Analysis

Figure 8 provides behavioral evidence that WebShaper-trained agents execute more complex information-seeking strategies than agents trained on alternative datasets. The analysis compares distribution of tool calls (Search, Visit, and Total) across WebShaper, E2HQA, and MHQA.

Search operations (Figure 8a):

• WebShaper shows a "pronounced long-tail distribution" with "pretty much tasks requiring over 3 search operations" (Section 4.3.6). The paper claims this is "3-4x higher than E2HQA and MHQA."
• This suggests WebShaper questions genuinely require multi-query exploration rather than single-shot retrieval.

Visit operations (Figure 8b):

• WebShaper "maintains a high ratio for trajectories exceeding 3 steps, while competing datasets sharply drop after 10 steps."
• The sustained page-visiting behavior indicates deeper navigation through web content.

Total tool calls (Figure 8c):

• WebShaper "doubles the count larger than 3" compared to baselines and "sustains non-zero proportions up to 30 tool calls."
• This is the most direct evidence that WebShaper questions require longer, more complex reasoning trajectories than information-driven dataset questions.

Critical reading of these claims: The paper states these findings qualitatively but does not provide specific numbers — we are told "3-4x higher" and "doubles the count" without exact ratios or statistical comparisons. The histograms in Figure 8 are suggestive but lack axis labels precise enough for verification. More importantly, longer trajectories are not necessarily better trajectories — an agent that executes 30 tool calls might be inefficiently flailing rather than demonstrating sophisticated reasoning. Without showing that the success rate of long trajectories is high, the tool call count alone is an ambiguous signal. The paper implicitly assumes that more tool calls = more complex reasoning, but alternative explanations (inefficiency, difficulty finding information, getting stuck in loops) are not ruled out.

Ablation Studies and Robustness Checks

Formalization vs. natural language synthesis: Figure 7a compares WebShaper's formalization-driven synthesis ("FL") against a variant that uses natural language throughout the synthesis process ("NL"). Both use the same Expander agent, but FL guides expansion with the KP representation while NL prompts the Expander with the current question in natural language. Across all three backbones (Qwen-2.5-32B, Qwen-2.5-72B, QwQ-32B), FL consistently outperforms NL. The paper states that this "indicate[s] that our formalization language can mitigate the limitations incurred by natural language" and reduces error propagation during synthesis. The magnitude of the advantage at each backbone is shown in Figure 7a but specific numbers are not provided in the text.

This ablation is central to the paper's thesis because it isolates the effect of formalization from other aspects of the pipeline (Expander agent, web search during synthesis, layer-wise structure). If FL and NL performed similarly, the formalization would be decorative rather than functional. The consistent FL advantage supports the claim that formalization improves data quality, though the effect size (visible in Figure 7a bars) should be quantified.

Layer-wise vs. sequential expansion strategy: Figure 7b compares the layer-wise expansion strategy against a sequential expansion variant. Both use the same formalization and Expander, but sequential expansion extends the question chain linearly rather than traversing leaf constants layer by layer (Figure 4b vs. 4c). Layer-wise outperforms sequential across all three backbones. The paper interprets this as evidence that layer-wise structure "truly mitigates shortcomings such as Redundancy and Reasoning shortcuts" (Section 4.3.5).

This ablation validates a key design claim: even with formalization, the order of expansion matters. The sequential variant should be susceptible to reasoning shortcuts (where a new KP connects a constant directly to a variable near the target), and its underperformance relative to layer-wise supports this hypothesis, though the paper does not provide explicit shortcut analysis on the generated data.

Effect of training dataset on tool-call behavior: While not framed as an ablation, the comparison in Figure 8 implicitly tests whether the WebShaper dataset induces different agent behaviors than E2HQA and MHQA. The substantially longer tool-call sequences and higher search/visit counts provide behavioral validation that WebShaper data teaches multi-hop reasoning rather than single-shot retrieval.

SFT-only vs. SFT+RL: Figure 6 shows that RL provides substantial gains on top of SFT for both model sizes and both benchmarks. This is important because it demonstrates the WebShaper dataset is not merely good for imitation learning — it provides a rich enough behavioral landscape that RL can discover reward-maximizing strategies beyond what SFT alone captures.

Dataset domain coverage: Figure 5 shows the domain distribution of the WebShaper dataset, demonstrating coverage across Sports, Politics, Entertainment, and other thematic areas. The paper argues this "deliberate design ensures our dataset not only avoids over-reliance on any single domain but also maintains sufficient sample density across diverse topics." However, the domain distribution is shown only for WebShaper — there is no comparison with the domain distributions of alternative datasets. Without this comparison, we cannot assess whether WebShaper's gains come from better domain coverage or from structural properties of the questions within domains.

Seed question filtering threshold: The paper uses a permissive 1-out-of-5 correct rollout criterion for retaining seed questions (Section 3.1). No ablation studies the effect of this threshold — would a stricter threshold (e.g., 3-out-of-5) improve data quality by removing harder-to-answer questions, or reduce diversity by eliminating challenging but valid questions? The choice of 5 rollouts and a 1-out-of-5 threshold seems arbitrary without supporting ablations.

Missing ablations: Several important design choices are not ablated:

• Number of expansion layers (l): Described as "a hyperparameter for controlling the task coverage and difficulty" (Section 3.2.2), but no experiments vary it to show how question difficulty and agent performance change with expansion depth. This is a notable gap since controllable complexity is claimed as a key advantage of the formalization-driven approach.
• Seed dataset size (18,000): No experiments show how performance varies with the number of seed questions. Would 9,000 seeds produce similar results? Would 36,000 improve further?
• Final trajectory count (5,000): The filtering from expanded questions to final trajectories is aggressive but unanalyzed. What is the yield rate at each filtering stage? Does more aggressive filtering improve quality at the expense of quantity?
• Validation threshold strictness: The non-triviality check in the Validate tool (whether an LLM can answer the sub-question without search) uses QwQ as the judge. What if a weaker or stronger model were used? Would using a stronger model for validation produce harder questions that further improve agent training?
• Effect of the summarization model: The Expander and trajectory-collection agent both use Qwen-2.5-72B for summarization. No ablation tests whether summarization quality affects final data quality — e.g., using a weaker summarizer might produce noisier trajectories that hurt training.
• Effect of RL algorithm choice: GRPO is used for RL. How does it compare to PPO, DPO, or simpler best-of-N rejection sampling from the SFT policy? The value of GRPO over alternatives is asserted but not demonstrated.

Critical Assessment

The central claim of this paper is that formalization-driven synthesis produces better training data for information-seeking agents than information-driven synthesis, and that the resulting models achieve state-of-the-art open-source performance. The experiments provide substantial but incomplete support for this claim. Here is what the experiments genuinely demonstrate, what they do not, and what would strengthen the case.

What the experiments demonstrate convincingly:

1. WebShaper-trained models outperform models trained on alternative datasets when all are fine-tuned on the same backbone with the same SFT procedure (Table 2). This is the cleanest comparison in the paper, since it controls for model, training recipe, and evaluation protocol, varying only the training data. The advantage is consistent across three backbones, with substantial margins on QwQ-32B (+7.7 over the next-best dataset) and moderate margins on Qwen-2.5-32B (+3.8). This supports the claim that WebShaper data is better for training IS agents than the information-driven alternatives tested.

2. RL on top of SFT provides substantial additional gains (Figure 6), demonstrating that the WebShaper dataset supports effective reinforcement learning — it is not merely an SFT-playground but contains behavioral diversity that RL can exploit. The larger gains on the 72B model (+13.5 points) are consistent with the interpretation that the dataset's structural complexity is better leveraged by larger models.

3. Formalization with layer-wise expansion outperforms both natural-language synthesis and sequential expansion (Figures 7a, 7b), providing evidence that both the formal representation and the expansion strategy independently contribute to data quality. This is methodologically important because it shows the gains are not attributable to a single design choice.

4. WebShaper-trained agents exhibit longer, more complex tool-use trajectories (Figure 8), consistent with the claim that the dataset teaches multi-hop reasoning rather than single-shot retrieval.

What the experiments do NOT demonstrate:

1. The contribution of formalization cannot be isolated from the contribution of the Expander agent. The natural-language ablation (Figure 7a) compares formalization-guided synthesis against natural-language-guided synthesis, but both use the same Expander agent that performs web search during synthesis. The information-driven baselines (WebWalkerQA, E2HQA, MHQA) were created with different synthesis procedures entirely — different models, different web corpora, different expansion methods. The paper would be stronger with an ablation that uses an information-driven synthesis methodology but adds the Expander agent's web-search-during-synthesis capability, to determine whether the gain comes from formalization or simply from better information retrieval during synthesis.

2. The claimed "controllable complexity" is never demonstrated experimentally. The paper states that the number of expansion layers l controls task difficulty, but no experiment varies l and shows that harder questions (deeper expansion) produce better (or worse) training data, or that models trained on deeper data perform better on harder evaluation questions. Without this demonstration, the claim of controllability is an architectural property, not an empirically validated feature.

3. The claimed advantage over human-curated data is not apples-to-apples. MHQA is described as "a composite dataset that integrates existing single-hop and multi-hop question-answering datasets. The majority of the questions are annotated by humans" (Section 4.1). This suggests MHQA was not designed specifically for IS agent training in the way WebShaper was — it may cover different domains, different question types, or different difficulty distributions. Comparing WebShaper to MHQA shows WebShaper is better for this specific training task, but does not show that synthetic formalization outperforms human annotation in general — a human-annotated dataset designed with equal care for IS agent training might close or reverse the gap.

4. Statistical significance is never addressed. The GAIA test set has 165 questions. A 1-point difference in average accuracy represents approximately 1.65 questions. With Level 3 having only ~12 questions, the 16.6% accuracy for all WebShaper backbones represents exactly 2 correct answers — one more correct answer would boost Level 3 to 25.0%. The reported gaps between methods (e.g., WebShaper 53.3 vs. WebDancer 51.5 on QwQ-32B) are small in absolute question-count terms. Without confidence intervals, we cannot assess whether these differences are reliable.

5. Compute efficiency is completely unaddressed. The paper reports accuracy but not inference cost. WebShaper-trained agents execute up to 30+ tool calls (Figure 8c), and each "Visit" action involves downloading full page content via Jina and summarizing with a 72B model. This is substantially more expensive per question than the baselines (which show shorter tool-call sequences in Figure 8). If WebShaper achieves +5 points of accuracy at 3× the inference cost, the practical value proposition changes. A compute-matched comparison (as seen in the reference example's FLOPs-matched analysis) would be informative.

6. Generalization beyond the training distribution is unexamined. All evaluation is on GAIA and WebWalkerQA. How well do WebShaper-trained agents perform on other IS benchmarks (e.g., BrowseComp, HotpotQA, Natural Questions with web access)? Does the formalization-driven training teach general IS skills or skills specific to the types of questions that the KP representation can express? The domain distribution (Figure 5) shows coverage of sports, politics, entertainment — but it's unclear whether the structure of WebShaper questions (intersections of KPs with layer-wise expansion) covers the structure of questions in other benchmarks.

What would strengthen the paper:

• A compute-matched comparison that gives baseline methods equivalent inference budgets and measures accuracy as a function of compute (as in the reference example's Figure 4 and Figure 9). This would reveal whether WebShaper's accuracy advantage comes from better strategy or simply more tool calls.
• A difficulty-calibration experiment varying expansion layers and measuring how training data depth affects model performance at each GAIA difficulty level. This would validate the controllability claim and inform curriculum design.
• A held-out benchmark evaluation (e.g., BrowseComp) to test whether WebShaper-trained agents generalize or whether the formalization restricts the learned skills to KP-expressible question types.
• Confidence intervals on all reported numbers, particularly given the small GAIA test set.
• Ablation of the Expander's web search during synthesis — i.e., generate questions using the formalization + expansion strategy but with the Expander limited to its parametric knowledge (no live search) versus the full Expander with search. This would measure how much of the gain comes from the structural formalization versus the fact that synthesis-time search discovers facts the training distribution doesn't otherwise contain.
• Analysis of synthesis cost. The Expander performs web searches, page visits, LLM summarization, and multiple validation calls for each expansion step. The paper never reports the computational cost of generating the 5,000 final trajectories, which matters for reproducibility and practical adoption.

In summary, the experiments robustly show that WebShaper produces training data superior to the specific information-driven alternatives tested, and that this superiority translates to state-of-the-art open-source performance on GAIA and WebWalkerQA. The experiments do not isolate whether the performance gain is primarily due to formalization, better information retrieval during synthesis, deeper question structures, or simply more compute expended during both synthesis and inference. The paper's broader claims about formalization enabling controllable complexity and systematic coverage are architecturally plausible but empirically underexplored.

6. Limitations and Trade-offs

Capability Ceiling on Hard Problems: No Gains on the Most Difficult Benchmark Tier

The assumption or constraint: The paper's formalization-driven synthesis generates training data through recursive composition of Knowledge Projections. This procedure assumes that complex questions can be constructed by iteratively composing simpler ones — that deeper reasoning reduces to more KPs intersected. The approach fails to generate training data for problems outside the compositional reach of the base seed questions and the Expander's ability to discover KP structures in web content.

The consequence: The most striking evidence is the complete stagnation on GAIA Level 3 questions. Across all three WebShaper backbones — Qwen-2.5-32B, QwQ-32B, and Qwen-2.5-72B — the accuracy on GAIA Level 3 is identically 16.6% (Table 1). This is not a model capacity limitation (otherwise the 72B model would score higher than the 32B model) but a data limitation: scaling model size provides zero improvement on the hardest questions because the training data contains no examples at that complexity tier. The gap with proprietary systems on Level 3 is stark — OpenAI Deep Research achieves 47.6%, nearly 3× higher — suggesting that WebShaper's formalization space simply does not cover the reasoning patterns required for the hardest GAIA questions. The paper does not analyze what types of Level 3 questions WebShaper fails on, but the flat accuracy across all model scales strongly implies a coverage ceiling: the synthesis pipeline cannot produce questions that require the reasoning depth or type demanded by GAIA's hardest tier.

What evidence exists in the paper: Table 1 shows the identical 16.6% Level 3 score across three backbones with substantially different overall capabilities (52.4, 53.3, and 60.1 average GAIA scores for the three variants). The paper never explicitly discusses this plateau, but the numbers speak clearly: further scaling of model capacity yields zero marginal benefit on the hardest problems. Figure 9 (case study) shows a question with 6 triplets — but GAIA Level 3 questions may require reasoning structures (temporal reasoning across multiple time periods, contradictory source resolution, mathematical computation interleaved with fact retrieval) that are not naturally expressed as intersections of Knowledge Projections. The tool call analysis (Figure 8c) shows the distribution extending to 30+ calls, but this measures execution complexity, not the structural complexity of the underlying reasoning graph — an agent can make 30 calls on a structurally shallow question by being inefficient, or fail on a structurally deep question with only 5 calls if those calls don't retrieve the necessary information.

Mitigation status: The paper does not acknowledge this ceiling explicitly. Section 2 defines the IS formalization as a universal framework but never discusses what types of reasoning it excludes. The layer-wise expansion hyperparameter l is described as controlling difficulty (Section 3.2.2), but no experiment varies l to determine whether increased depth would eventually cover GAIA Level 3 patterns or whether those patterns lie outside the KP formalism entirely. The paper makes no suggestion for future work on extending the formalization to cover harder reasoning types.

Difficulty Estimation Cost Is the Elephants in the Room: Expander Synthesis Compute Is Unreported and Likely Enormous

The assumption or constraint: The entire WebShaper pipeline rests on the Expander agent autonomously searching the web, visiting multiple pages per constant, summarizing content with a 72B model, and running two LLM-based validation calls per sub-question — all executed repeatedly across thousands of seed questions, multiple expansion layers per question, and 5 rollouts per trajectory. Yet the paper reports zero quantitative information about the computational cost of this synthesis process.

The consequence: This omission matters profoundly for practical adoption. The headline claim — that WebShaper produces training data superior to existing datasets — provides no information about whether the cost of producing that data is prohibitive. The Expander's ReAct loop involves, for each expansion of each leaf constant: (a) multiple Google Search calls, (b) Visit actions that download full web pages via Jina and summarize them with Qwen-2.5-72B (a 72-billion-parameter model), (c) two separate QwQ calls for the Validate tool (type consistency check + non-triviality check), and (d) the final answer construction. If each expansion step involves, say, 3 search queries returning 10 URLs each, visiting 5 of those URLs with full-page summarization, plus 2 QwQ validation calls — that is hundreds of thousands of LLM inference calls plus web API costs to generate 5,000 final trajectories. Without cost reporting, a practitioner cannot assess whether WebShaper's data synthesis is 2×, 10×, or 100× more expensive than information-driven alternatives that use single-pass LLM generation from pre-collected content. The paper's own comparison datasets — WebWalkerQA (generated from random walks with LLM question generation) and E2HQA (LLM-based question expansion from pre-collected information) — are vastly cheaper to produce, since they do not involve agentic web interaction during synthesis. If WebShaper costs 50× more to synthesize than E2HQA but provides +3.8 points on GAIA (Table 2, Qwen-2.5-32B), the cost-benefit tradeoff is unclear.

What evidence exists in the paper: None. The paper never mentions synthesis cost in terms of API calls, GPU hours, wall-clock time, or dollar amount. Appendix A describes the "Visit" tool's summarization using Qwen-2.5-72B, and the Expander agent's tools (Section 3.2.3), but never aggregates these into a total cost. The seed filtering step (Section 3.1) notes that 5 rollouts are performed per question using the WebDancer framework — itself a non-trivial cost — and only questions with at least one correct rollout are retained, implying that most rollouts (and their compute) were discarded. The trajectory filtering (Section 3.3) reduces "18,000 seed questions, each expanded through multiple layers, each with 5 rollouts" to just 5,000 final trajectories — a massive reduction that implies enormous discarded compute, but the paper provides no yield ratios. This is not a minor reporting oversight; it is a fundamental omission that prevents evaluation of the method's practicality for any organization without effectively unlimited compute budgets.

Mitigation status: The paper does not acknowledge synthesis cost as a limitation at all. There is no cost analysis, no suggestion for reducing Expander overhead (e.g., caching, cheaper models for validation, reducing rollout counts), and no comparison of synthesis cost against alternative data generation approaches. The paper frames WebShaper as democratizing access to high-quality agent training data (Section 1's emphasis on open-source), but without cost reporting, it is unclear whether the method is practical for resource-constrained academic or startup settings — exactly the settings that most need open-source alternatives to proprietary systems.

Formalization Expressiveness: The KP Framework Cannot Represent Justifications, Uncertainty, or Soft Constraints

The assumption or constraint: The Knowledge Projection formalism models information-seeking tasks as set-theoretic queries: the answer is an entity set T defined by the intersection of KPs under specific relations. This representation captures hard constraints (an entity is either in the set or not) with deterministic relations (bornIn, playAt, foundIn). The paper's Proposition 1 (distributive law for R-Union) further assumes that relations compose cleanly with set operations — that R(S1 ∪ S2) = R(S1) ∪ R(S2).

The consequence: Many real-world information-seeking tasks require reasoning that the KP formalism cannot express, including:

• Justificatory reasoning: Questions like "Why did the Berliner FC Dynamo decline after German reunification?" cannot be reduced to finding an entity set. The answer is an explanation — a causal chain, not an intersection of KPs. The formalism fundamentally represents what questions (what entities satisfy these constraints?) but not why or how questions.

• Uncertainty and conflicting sources: Real web search involves contradictory information from different sources. An IS agent must sometimes answer "the evidence is mixed" or "Source A says X while Source B says Y." The KP formalism has no representation for uncertainty, conflicting evidence, or source reliability — an entity either satisfies a relation or it doesn't. An Expander constructing a sub-question can only validate that the entity is of the correct type (Section 3.2.3: "it checks if the type of C satisfies the sub-question"), not whether the supporting evidence is robust.

• Soft or graded constraints: Questions like "Which players had the most successful careers after leaving Berliner FC Dynamo?" involve ranking and judgment — what does "most successful" mean? The KP formalism represents binary set membership, not graded relevance. The non-triviality check in the Validate tool rejects questions answerable by LLMs without search (Section 3.2.3), but has no mechanism for distinguishing between a clear-cut answer and one requiring weighted evidence synthesis.

The practical consequence is that WebShaper-trained agents are likely brittle on question types outside the KP subspace. The evaluation benchmarks (GAIA, WebWalkerQA) are heavily skewed toward factual lookup and multi-hop entity retrieval — exactly the type of question the KP formalism excels at representing. The paper provides no evidence that WebShaper training transfers to explanation, comparison, opinion-synthesis, or uncertainty-aware question types. If a user asks a WebShaper-trained agent "Why did event X happen?", the agent may attempt to force it into a KP-style answer (find entities with relation causedBy) even when the question requires synthesis of narrative explanations across sources.

What evidence exists in the paper: The case study in Figure 9 perfectly illustrates the formalism's sweet spot: a question requiring identification of an entity (a section title) through nested constraints across multiple relations. Every constraint is a hard, verifiable fact. The natural language rendering is ungainly ("What is the title of the section, where the section is written by an author who also authored...") precisely because it's forcing an intersection-of-KPs structure into prose. This works for the question type GAIA tests, but the paper does not discuss what fraction of real-world IS tasks fall into this category. The domain distribution (Figure 5) shows coverage of "Sports, Politics, and Entertainment" — but these are topic domains, not reasoning types. A political question like "What are the main arguments for and against policy X?" requires reasoning that the KP formalism cannot represent, regardless of which domain the entities come from.

Mitigation status: The paper does not discuss the expressiveness boundaries of the KP formalism. It presents the formalization as a general framework for information-seeking (Section 2) without enumerating what types of reasoning it excludes. Section 8 (Future Work) does not mention extending the formalization beyond set-theoretic operations. The title claims the framework is for "Information-Seeking" without qualification, but the actual coverage is more accurately described as entity-retrieval under hard conjunctive constraints.

Single Benchmark Family, Single Task Type: No Evidence of Generalization Beyond GAIA-Style Factual Retrieval

The assumption or constraint: All evaluation is conducted on exactly two benchmarks: GAIA (165 test questions) and WebWalkerQA (size unspecified). Both benchmarks test the same fundamental skill — multi-hop factual retrieval from web sources with a deterministic correct answer. The paper implicitly assumes that performance on these benchmarks generalizes to information-seeking tasks broadly, and that the WebShaper training data teaches general IS capabilities rather than benchmark-specific patterns.

The consequence: This is a single-task evaluation masquerading as a general capability evaluation. The domain distribution (Figure 5) shows WebShaper covers sports, politics, entertainment, etc., but domain diversity is not task diversity. A model trained exclusively on entity-retrieval questions may perform well on any entity-retrieval benchmark (GAIA, WebWalkerQA) while failing completely on explanation, comparison, summarization, or open-ended research tasks — all of which are equally valid "information-seeking" behaviors and are central to real-world use cases like Deep Research. The paper does not evaluate on:

• BrowseComp (Wei et al., 2025): A benchmark specifically designed to test browsing agents on questions that require synthesizing information from multiple pages, including questions with hidden answers.
• HotpotQA or Natural Questions with web access: Standard multi-hop QA benchmarks that would test generalization to different question distributions.
• Any open-ended or explanation task: Questions requiring an answer that is not a named entity or short phrase.

The risk is that WebShaper's formalization is not merely a helpful inductive bias but a constraint — the model learns to represent all questions as intersections of KPs, which works beautifully for KP-structured questions but catastrophically for questions requiring other reasoning patterns. Without evaluating on non-KP-structured tasks, we cannot distinguish between "WebShaper teaches general IS skills" and "WebShaper teaches excellent performance on the specific task type its formalization can express."

What evidence exists in the paper: The only evidence of generalization is that WebShaper works across two benchmarks (GAIA and WebWalkerQA) and three model backbones. But both benchmarks are from the same narrow distribution — in fact, WebWalkerQA was created by overlapping authors (Wu et al., 2025b) and shares methodological DNA with the WebShaper approach. The consistent backbone-to-backbone patterns (WebShaper on Qwen-2.5-72B is always best, WebShaper always outperforms WebDancer) suggest the evaluation is internally consistent but provide no signal about external validity. The paper does not claim to test generalization beyond these benchmarks, but the framing ( "WebShaper achieves state-of-the-art performance among open-sourced IS agents") implies generality that the evaluation does not support.

Mitigation status: The paper does not acknowledge this as a limitation. The abstract and introduction present WebShaper as a general IS data synthesis framework, not as a method specialized for GAIA-style multi-hop retrieval. There is no discussion of what task types fall outside the evaluation scope or plans for broader benchmarking. The related work section (Section 5.1) discusses other IS benchmarks (BrowseComp, BrowseComp-zh) but only as "test sets" that "restrict applicability for training agents" — not as potential evaluation targets for testing generalization.

The Small GAIA Test Set Makes Accuracy Estimates Unreliable and Rankings Potentially Meaningless

The assumption or constraint: The paper's primary evaluation benchmark, GAIA, contains only 165 questions total, split across three difficulty levels. The paper reports Pass@1 accuracy as percentages to one decimal place but provides no confidence intervals, no standard deviations, and no statistical significance tests for any comparison. The Level 3 subset is particularly small — the 16.6% accuracy that all three WebShaper backbones achieve likely represents exactly 2 correct answers out of approximately 12 questions (given that Level 3 scores in Table 1 appear in increments of ~8.3 percentage points).

The consequence: This makes many of the paper's comparative claims statistically fragile. A single additional correct answer on GAIA Level 3 would change WebShaper-72B's score from 16.6% to 25.0% — a 8.4 percentage point swing that would substantially change the average score and the narrative about Level 3 stagnation. The claim that WebShaper-72B's 60.1% average "excels second-best method WebSailor 4.7 score" (Section 4.2) represents a difference of approximately 7-8 questions out of 165 — meaningful if real, but we have no way of knowing whether it would replicate on a different test set or even on a different random split of the same data. The comparison between WebShaper (53.3) and WebDancer (51.5) on QwQ-32B is a difference of roughly 3 questions — well within the range of sampling variability for a 165-question test.

The same issue applies to the data comparison (Table 2). WebShaper vs. E2HQA on Qwen-2.5-72B is 45.6 vs. 44.6 — a one-question difference. On Qwen-2.5-32B, it's 43.6 vs. 39.8 — a difference of roughly 6 questions, which is more convincing but still without any measure of uncertainty.

What evidence exists in the paper: The GAIA test set size (165) is known from the GAIA paper (Mialon et al., 2023), which the paper cites. The resolution of the reported percentages reveals the subset sizes: Level 3 scores of 0.0, 8.3, 16.6, and 25.0 in Table 1 correspond to increments of 1/12 ≈ 8.3%, implying approximately 12 Level 3 questions. Level 2 scores show finer granularity (e.g., 50.0, 53.8, 63.4), suggesting roughly 50-55 questions. Level 1 scores show even finer granularity, suggesting roughly 100 questions. The paper does not report these breakdowns explicitly, but the percentage patterns make the small sample sizes evident. The paper provides no error bars on any figure (Figures 6a, 6b, 7a, 7b all show bar charts with no uncertainty visualization).

Mitigation status: The paper does not acknowledge the small test set as a limitation, nor does it attempt to quantify uncertainty. This is a common practice in the agent benchmarking literature (GAIA is a standard benchmark and its size is fixed), but it is nonetheless a significant limitation for interpreting the results. The standard remedy — bootstrap confidence intervals, reporting exact counts alongside percentages, or using multiple evaluation runs with different random seeds — is not applied. The paper's claim to "state-of-the-art performance" rests on comparisons that are statistically indistinguishable from noise for several key pairwise comparisons.

Compute-Matched Comparison Is Absent: WebShaper Trajectories Are Much Longer Than Baselines, and the Accuracy Gain May Be Purchased with Extra Inference Compute

The assumption or constraint: The paper reports only final accuracy, not the inference compute expended to achieve that accuracy. WebShaper-trained agents execute substantially more tool calls than baseline agents (Figure 8: "WebShaper's doubles the count larger than 3" compared to E2HQA and MHQA in total tool calls). Each tool call involves LLM inference for thought generation, search query formulation, and response parsing, plus external API calls (Google Search, Jina page fetching, Qwen-2.5-72B summarization for Visit actions). The paper makes no attempt to control for or report total inference cost.

The consequence: The reported accuracy comparisons confound two effects: (1) better strategy (WebShaper-trained agents make smarter decisions about what to search for and which pages to visit) and (2) more compute (WebShaper-trained agents simply execute more tool calls because their training data contained longer trajectories). If WebShaper achieves +5 points of accuracy using 3× the tool calls of WebDancer, the comparison is not a pure measure of agent capability — it partially reflects a decision to trade compute for accuracy, which any baseline could also do simply by increasing its rollout budget or allowing more search iterations. The paper's framing implies that WebShaper teaches better strategies, but the evidence equally supports the interpretation that WebShaper teaches agents to be more persistent (or less efficient) in their searching — executing more operations until they find the answer. Without a compute-matched comparison (e.g., accuracy vs. total tool calls budget, or accuracy vs. LLM inference tokens), we cannot distinguish these explanations.

There is also a fairness concern in the baseline comparisons. The baseline models in Table 1 are evaluated under whatever tool-use budget their respective frameworks specify — Search-o1, WebDancer, and WebThinker may impose different limits or termination conditions. If WebShaper's ReAct agent runs without a hard tool-call limit while baselines have conservative cutoffs, the accuracy advantage may partly reflect a different evaluation protocol rather than better training data.

What evidence exists in the paper: Figure 8 is the critical evidence. The tool call distributions show that WebShaper trajectories are systematically longer — higher proportions of trajectories with many search calls (Figure 8a), many visit calls (Figure 8b), and many total calls (Figure 8c). The paper interprets this positively: "superior handling of information-rich queries requiring iterative refinement" and "enhanced navigational intelligence." But these are descriptions, not causal explanations. An equally valid interpretation is that WebShaper training data contained longer trajectories (since the Expander generated deep multi-hop questions), so the model learned that long trajectories are normal and expected, regardless of whether they are necessary for a given question. The paper provides no analysis of the marginal utility of additional tool calls — does accuracy increase with call count, and if so, does it plateau? Does WebShaper achieve higher accuracy than WebDancer at the same number of tool calls, or only at higher call counts?

Mitigation status: The paper does not address the compute-accuracy tradeoff. It does not report total inference cost for any method, does not control for tool-call budget in the evaluation, and does not provide accuracy-vs-compute curves. The discussion section (Section 4.3.6) celebrates WebShaper's longer trajectories without considering efficiency as a dimension of agent quality — a striking omission given that practical deployment of IS agents is heavily constrained by inference cost and latency. The paper's approach to efficiency reporting is in marked contrast to the reference example, which carefully accounts for generation budgets and FLOPs throughout its evaluation, enabling precise statements about compute-optimal scaling.

7. Implications and Future Directions

How This Work Changes the Landscape

WebShaper introduces formalization-driven synthesis into a field that has been implicitly operating under an information-driven paradigm without recognizing its limitations. The paper's contribution is not a single technique but a methodological reframing: it demonstrates that treating information-seeking tasks as formal objects (set-theoretic expressions over Knowledge Projections) before collecting any web content fundamentally changes what is possible in data synthesis — enabling mechanical validation of question structure, systematic control over reasoning depth, and elimination of entire classes of synthesis errors (redundancy, reasoning shortcuts) that plague information-driven approaches.

The magnitude of this shift warrants careful characterization. It is not a paradigm shift in the Kuhnian sense — the field of agent training data synthesis is too young for entrenched paradigms to have accumulated the kind of anomalies that precipitate revolutionary science. Rather, it is a diagnostic reframing that explains why prior approaches underperformed and provides a constructive alternative with demonstrably better properties. The paper shows that information-driven synthesis suffers from two systematic pathologies — structural inconsistency between collected information and generated questions, and homogeneity of reasoning structures due to unguided web crawling — and that these pathologies are not incidental but are inherent to the information-first workflow. By inverting the pipeline (formalize first, collect second), WebShaper removes these failure modes at the architectural level rather than attempting to filter them out post-hoc.

This reframing has already begun to reorganize the research landscape in a specific way: it moves the central challenge of IS data synthesis from better information retrieval during synthesis to better formal task representations. Prior work (WebDancer, WebWalkerQA, WebSailor) focused on improving how information is collected and organized — better web crawls, richer graph structures, coreference networks. WebShaper's results (Table 2: +3.8 to +7.7 points over the best information-driven datasets across backbones) suggest that these improvements hit diminishing returns because they address the wrong bottleneck. The formalization-driven approach achieves larger gains by addressing the structural correctness of the generated questions, not the richness of the collected information. This redirects research effort toward formal representation design — what set-theoretic or logical constructs best capture the reasoning patterns of interest? — and away from crawling and content-organization strategies.

A particularly important reconciliation the paper enables is between two conflicting intuitions in the agent training community. Intuition 1: Synthetic data will inevitably contain errors and structural flaws, so we should invest in better filtering and quality estimation. Intuition 2: The diversity and scale of synthetic data matter more than per-example quality, so we should accept noise and rely on scale to wash it out. WebShaper's layer-wise expansion strategy (Section 3.2.2, Figure 4) shows that certain structural flaws — shortcuts, redundancies — are preventable by design if the synthesis process respects a formal representation of the desired reasoning topology. The ablation in Figure 7b confirms that this matters: even with the same formalization and Expander agent, a sequential expansion strategy that can introduce shortcuts underperforms layer-wise expansion that cannot. This suggests that the right synthesis architecture can eliminate the tension between quality and scale — you can have both if you build structural correctness into the generation process itself.

The paper also resolves a latent tension between the information-seeking agent community and the formal reasoning community (Theorem proving, KBQA). The formal reasoning community has long used formal languages as targets — translate natural language into Lean 4, then verify proofs mechanically. The agent community has treated web-based tasks as inherently informal — the web is messy, so agents must learn to cope with messiness through scale and RL. WebShaper demonstrates a middle ground: a formal language designed not for verification of completed solutions but for prescriptive synthesis of training tasks. The formalization constrains the generation process, not the evaluation process. This opens a design space that neither community has systematically explored — formalisms engineered for the capabilities of LLM-based synthesizers rather than for human understanding or mechanical proof checking.

The downstream consequence is that verifier quality is no longer the sole bottleneck for data synthesis. In the information-driven paradigm, you generate questions from collected content and then must somehow verify their structural correctness — but the verifier (typically an LLM judge) has no access to the intended reasoning structure, only to the question text and answer. WebShaper's Validate tool (Section 3.2.3) operates on the formal representation, enabling mechanical checks (type consistency, non-triviality) that are impossible to perform reliably on natural language alone. This shifts attention from post-hoc verification to synthesis-time validation — embedding correctness checks inside the generation loop where they have access to the structural specification.

Finally, the paper changes the conversation around difficulty calibration for agent training data. Prior approaches treat difficulty as an emergent property that can be estimated post-hoc (by model loss or human judgment) but not designed. WebShaper's layer-wise expansion hyperparameter l (Section 3.2.2) provides a direct, causally interpretable difficulty knob — more expansion layers strictly increase the minimum hop distance between any leaf constant and the target, which strictly increases the number of intermediate entities the agent must resolve. Whether this causal measure of difficulty translates into behavioral difficulty for the trained agent is partially validated by the tool call analysis (Figure 8: WebShaper agents execute more operations), but the broader implication is that curriculum learning for IS agents becomes engineerable rather than a matter of post-hoc data sorting. The paper does not fully realize this capability (it reports results for a single dataset, not a difficulty-stratified curriculum), but the architecture provides the vocabulary and mechanisms for doing so.

Follow-Up Research This Work Enables

Direct measurement of formalization's causal contribution to data quality, decoupled from Expander web search. The paper's natural-language ablation (Figure 7a) compares formalization-driven synthesis against synthesis where the Expander receives and produces natural language questions throughout. However, both conditions use the same Expander agent with the same web search capability. The critical unanswered question is: does formalization improve data quality per se, or does it merely enable the Expander to search more effectively during synthesis (because the KP representation gives it clearer search targets)? A clean ablation would compare WebShaper's full pipeline against a variant where the Expander uses the formalization for question structure but is denied web access during synthesis — it must construct sub-questions using only the parametric knowledge of the LLM (analogous to how the seed questions are generated from Wikipedia content without live search). If this variant performs close to the full pipeline, the gain is primarily from formal structure, not from synthesis-time information retrieval. If it performs close to the NL baseline, the gain is primarily from the Expander's web access, and the formalization's role is enabling better search rather than better structure. This distinction matters both for understanding why WebShaper works and for designing cheaper synthesis pipelines — if formalization alone provides most of the gain, the expensive web search during synthesis can be reduced or eliminated.

Extending the KP formalism to represent justificatory, comparative, and uncertainty-aware question types. Section 6 identified that the KP formalism represents what questions (what entities satisfy constraints?) but not why, how, or how reliable questions. A natural extension is to augment the formalism with justification predicates — e.g., justifiedBy(claim, source) or contradicts(source_A, source_B) — that would enable synthesis of questions requiring explanation or evidence synthesis. The synthesis challenge is that these predicates do not have clean set-theoretic semantics; they require modeling relations between propositions not just entities. A strong follow-up would define a minimal extension to the KP formalism that captures one new reasoning type (e.g., comparative questions: "Which of X and Y is larger according to source Z?") and demonstrate that (a) the Expander can reliably synthesize such questions using the extended formalism, and (b) agents trained on the resulting data outperform agents trained on KP-only data at the new question type, without regressing on standard entity retrieval. The risk of such extensions is that they compromise the simplicity that makes the current formalism operationalizable by LLMs — Proposition 1's distributive law, which simplifies R-Union, may not have analogues in richer logics. The tension between expressiveness and LLM-operability is a research problem in itself.

Difficulty-stratified curriculum learning using expansion layer count as the difficulty parameter. The paper claims that the number of expansion layers l controls task complexity (Section 3.2.2) but never varies l experimentally. A direct follow-up would train agents on datasets synthesized with l = 1, 2, 3, 4 (or until synthesis yield drops due to Expander failure) and measure performance on GAIA difficulty levels as a function of training depth. The prediction: deeper training data improves performance on harder evaluation questions (GAIA Levels 2-3) but may not help (or may even hurt, via distribution shift) on easier questions (GAIA Level 1). If this prediction holds, curriculum learning becomes straightforward: train first on l=1 data, then l=2, then l=3, measuring held-out performance after each stage. If the prediction fails — if deeper data doesn't improve hard-question performance — this would reveal that the KP formalism has an expressiveness ceiling: past some depth, the formalism can't represent the reasoning patterns in hard GAIA questions, and further expansion just produces more elaborate examples of the same reasoning type. This negative result would be equally informative, clarifying the formalism's boundaries.

Cross-benchmark generalization testing to determine whether WebShaper teaches general IS skills or KP-specific patterns. The current evaluation on GAIA and WebWalkerQA tests performance on benchmarks that share the entity-retrieval-under-conjunctive-constraints structure that the KP formalism naturally represents. A stress-test evaluation on BrowseComp (Wei et al., 2025) — which includes questions requiring synthesis across pages with hidden or contradictory answers — and on explanation-oriented subsets of existing QA datasets (e.g., "Why" questions from Natural Questions, if extractable) would reveal whether WebShaper-trained agents have learned general information-seeking or have specialized to the KP template. If WebShaper agents underperform baselines on non-KP-structured tasks despite their strong GAIA performance, this would indicate that the formalization is a constraint as well as an enabler — the model overfits to the reasoning patterns the formalism can express. The follow-up's contribution would be precisely characterizing the generalization boundary: which types of IS tasks benefit from WebShaper training, which are unaffected, and which are harmed? This would guide practitioners in deciding when to use WebShaper versus alternative datasets.

Compute-matched evaluation of WebShaper-trained agents against baselines to disentangle strategy quality from inference persistence. Figure 8 shows WebShaper agents execute more tool calls than baselines, but Section 6 argued this confounds better strategy with more compute. A rigorous follow-up would evaluate all methods — WebShaper, WebDancer, WebThinker, Search-o1 — under a fixed inference budget, varying that budget parametrically. The budget could be measured in total tool calls allowed, total LLM inference tokens generated, or total wall-clock time (accounting for external API latency). The key outcome is an accuracy-vs-compute curve for each method, analogous to the test-time compute scaling curves in the reference example's Figure 3 and Figure 4. This would answer: does WebShaper achieve higher accuracy than WebDancer at the same compute budget, or only at higher budgets? If the former, WebShaper teaches genuinely better strategies. If the latter, the accuracy advantage is partially or wholly attributable to longer search persistence, and the practical value proposition depends on the cost of additional inference relative to the accuracy gain. This evaluation is essential before any organization adopts WebShaper for production agent training, since deployment decisions depend on the entire cost-accuracy frontier, not just the accuracy at whatever budget each method happens to use.

Analysis of synthesis yield and cost scaling to determine practical deployment feasibility. The paper reports producing 5,000 final trajectories from 18,000 seed questions (Section 3.3) but provides no intermediate yield ratios or cost figures. A practical follow-up would instrument the synthesis pipeline to report: (a) seed question yield after filtering (what fraction of random-walk-generated questions pass the 1-of-5 rollout criterion?), (b) per-expansion-step success rate (what fraction of Expander invocations produce valid sub-questions?), (c) trajectory yield after filtering (what fraction of rollouts are retained by correctness and quality filters?), and (d) total compute cost in LLM inference calls, web API calls, and GPU hours. With these numbers, a researcher can estimate the cost to reproduce WebShaper's dataset and can compare cost-effectiveness against alternative data generation approaches. A particularly valuable analysis would examine how yield and cost scale with expansion depth l — if the Expander's success rate degrades sharply for l > 3, this would place a practical ceiling on question complexity regardless of the formalism's theoretical expressiveness. This analysis would also reveal which pipeline stages dominate cost, guiding efforts to reduce synthesis expense (e.g., if validation calls dominate, more efficient validation heuristics could be developed).

Practical Applications and Downstream Use Cases

Training data generation for open-source Deep Research systems. The most direct application is to use WebShaper's pipeline to produce SFT datasets for organizations building open-source alternatives to proprietary systems like OpenAI Deep Research (67.4% GAIA) and Gemini Deep Research. The paper demonstrates that WebShaper-trained Qwen-2.5-72B achieves 60.1% on GAIA — the only open-source system surpassing 60 points and closing roughly half the gap to proprietary systems (Section 4.2, Table 1). An organization with access to a 72B-parameter model and the compute budget to run the Expander synthesis pipeline (cost unknown but likely substantial, as discussed in Section 6) could replicate this result, producing a competitive deep research agent without access to proprietary training data. The key practical consideration is the synthesis cost — organizations must weigh the one-time cost of running the WebShaper pipeline against the recurring cost of using proprietary APIs or the performance penalty of inferior training data. Without cost reporting in the paper, this calculation requires independent estimation, but the existence of a demonstrated recipe is itself valuable.

Curriculum-based agent training for progressive capability development. Although the paper does not demonstrate curriculum learning experimentally, the architecture supports it directly. A research lab training an IS agent could run the WebShaper pipeline with increasing expansion layers l = 1, 2, 3, ... to produce datasets of progressively deeper reasoning questions. The agent would be fine-tuned first on shallow data (single-hop questions: one intersection of KPs, no recursion), then on medium data (recursive KPs with intermediate variables), then on deep data (multiple recursive layers). The expected benefit is more efficient learning — the agent masters simple retrieval before tackling multi-hop composition — and potentially better final performance, since curriculum learning often outperforms training on the full difficulty distribution from the start. The paper's tool call analysis (Figure 8) shows that WebShaper questions demand substantially longer reasoning chains than alternative datasets; a curriculum would help the agent build up to these long chains gradually rather than attempting them from the beginning of training. The practical requirement is only that the synthesis pipeline be run multiple times with different l values, which reuses the same infrastructure.

Automated generation of domain-specific research agents. WebShaper's Expander agent synthesizes questions by searching the open web for information about specific constants and composing that information into formal sub-questions. This process can be targeted to a specific domain by initializing the seed question pool with domain-specific Wikipedia articles (e.g., biomedical articles, legal documents, financial reports) rather than random-walk-aggregated content. The expansion process would then produce complex multi-hop questions within that domain, training a specialized research agent. The benefit is that domain-specific agents often struggle with data scarcity — there are few human-annotated complex QA datasets for niche domains — but WebShaper can generate them synthetically as long as the domain's entity-relation structure is expressible in the KP formalism. The paper's domain distribution (Figure 5) shows coverage of sports, politics, and entertainment from a general Wikipedia seed pool; targeting the seed pool would shift this distribution. A legal research agent, for instance, could be trained on WebShaper-generated questions about case law precedents, statutes, and judicial appointments — all entity-relation structures that fit the KP template (case X cites case Y, statute Z applies to entity W, judge A appointed judge B).

Quality assurance for human-curated agent training datasets. Even for organizations that prefer human-annotated training data, WebShaper's formal validation tools (type consistency check, non-triviality check) can serve as automated quality filters. Human annotators or subject matter experts write complex information-seeking questions, which are then parsed into the KP representation (either manually or via an LLM-based parser) and validated using the same checks the Expander applies during synthesis. Questions that fail type consistency (the answer entity doesn't satisfy the question's constraints) or non-triviality (an LLM can answer without search) are flagged for human review or discarded. This application does not require running the full WebShaper synthesis pipeline — only the validation component, which is substantially cheaper. The benefit is reducing the error rate in human-curated datasets, where structural inconsistencies are common because humans, like LLMs, find it difficult to maintain reasoning consistency across multi-hop questions without a formal representation (as evidenced by MHQA's underperformance relative to WebShaper in Table 2: 41.7 vs. 53.3 on QwQ-32B). The validation tools provide a structural "linter" for IS questions that catches errors humans miss.