Sample, Align, Synthesize: Graph-Based Response Synthesis with ConGrs

Sayan Ghosh; Shahzaib Saqib Warraich; Dhruv Tarsadiya; Gregory Yauney; Swabha Swayamdipta

cs.CLOct 3, 2025

Sample, Align, Synthesize: Graph-Based Response Synthesis with ConGrs

Authors: Sayan Ghosh, Shahzaib Saqib Warraich, Dhruv Tarsadiya, Gregory Yauney, Swabha Swayamdipta

Organizations: Thomas Lord Department of Computer Science, University of Southern California

Abstract

Language models can be sampled multiple times to access the distribution underlying their responses, but existing methods cannot efficiently synthesize rich epistemic signals across different long-form responses. We introduce Consensus Graphs (ConGrs), a flexible DAG-based data structure that represents shared information, as well as semantic variation in a set of sampled LM responses to the same prompt. We construct ConGrs using a light-weight lexical sequence alignment algorithm from bioinformatics, supplemented by the targeted usage of a secondary LM judge. Further, we design task-dependent decoding methods to synthesize a single, final response from our ConGr data structure. Our experiments show that synthesizing responses from ConGrs improves factual precision on two biography generation tasks by up to 31% over an average response and reduces reliance on LM judges by more than 80% compared to other methods. We also use ConGrs for three refusal-based tasks requiring abstention on unanswerable queries and find that abstention rate is increased by up to 56%. We apply our approach to the MATH and AIME reasoning tasks and find an improvement over self-verification and majority vote baselines by up to 6 points of accuracy. We show that ConGrs provide a flexible method for capturing variation in LM responses and using the epistemic signals provided by response variation to synthesize more effective responses.

Figures & tables

Figure 1: Consensus Graphs ( ConGrs ) capture the variation in a set of sampled LM responses. A ConGr is a weighted DAG of: consensus nodes for text spans present in all responses and disagreement nodes for lexical differences between responses. A node’s weighted degree represents the fraction of responses which contain the information in that node. In the above example task of generating factual biographies from 3 sampled responses, disagreement nodes with lower weighted degree might indicate possible hallucinations. For this reason, none of the information in the disagreement nodes is included in the final synthesized response (further details in § 3 ).

Figure 2: Responses for a biography generation task from an aligned model (Qwen2.5-72B-Instruct) contain lexical overlap across ordered segments of responses compared to a shuffled baseline. Differences in lexical similarity (measured with Jaccard similarity over word sets) are significant as measured using a paired

t

-test for all quantiles.

Figure 3: From 1) a set of responses, we construct a ConGr by 2) using Needleman-Wunsch to construct a lexical DAG where each node’s text is a single token, 3) merging consecutive sequences of nodes that are present in all responses to create consensus nodes, 4) extracting paths between consecutive pairs of consecutive nodes and using an LM to create semantic equivalence classes, 5) creating a disagreement node for each semantic equivalence class.

Figure 4: Consensus decoding (left) uses a ConGr to combine text present in many responses. Guided self-verification (right) uses a ConGr to localize possible errors in reasoning chains.

Figure 5: Consensus decoding with ConGrs achieves the best trade-off between FActScore (the fraction of a response’s claims that are true) and the number of true claims provided. Up and to the right is better.

\tau

: selection threshold for consensus decoding.

\Theta

: the analogous parameter for the ASC baseline. Top row: Biography factuality. Bottom row: PopQA.

Method	FActScore	#T	#F	R	Mean # Tokens
ConGrs	$0.62$	$19.00$	$8.63$	$0.96$	$13,391.88$
UAD	$0.59$	$27.32$	$20.84$	$0.96$	$76,220.48$

Table 1: Consensus decoding with ConGrs uses 82% fewer tokens from secondary LMs compared to Uncertainty-Aware Decoding (UAD) ( Jiang et al., 2024 ) without sacrificing FActScore or response ratio. #T: mean number of facts deemed true in a response, #F: mean number of facts deemed false in a response, R: response ratio.

	False Presuppositions						Scientific References
	Qwen2.5-72B		Llama-3.3-70B		OLMo-2-32B		Qwen2.5-72B		Llama-3.3-70B		OLMo-2-32B
Method	R $\downarrow$	H $\downarrow$	R $\downarrow$	H $\downarrow$	R $\downarrow$	H $\downarrow$	R $\downarrow$	H $\downarrow$	R $\downarrow$	H $\downarrow$	R $\downarrow$	H $\downarrow$
Greedy	$0.22$	$0.16$	$0.66$	$0.49$	$0.00$	$0.00$	$0.78$	$0.67$	$0.32$	$0.30$	$0.50$	$0.41$
Mean of $m$	$0.25$	$0.17$	$0.62$	$0.46$	$0.01$	$0.01$	$0.76$	$0.66$	$0.28$	$0.26$	$0.61$	$0.54$
Shortest	$0.16$	$0.11$	$0.68$	$0.49$	$0.01$	$0.00$	$0.61$	$0.55$	$0.16$	$0.16$	$0.30$	$0.26$
LM Consensus	$0.33$	$0.23$	$0.70$	$0.51$	$0.02$	$0.01$	$0.33$	$0.29$	$0.29$	$0.26$	$0.08$	$0.07$

Table 2: Consensus decoding with ConGrs consistently achieves lower Response Ratio and Hallucination Score than other response synthesis methods on HALoGEN abstention tasks. R: Response Ratio, H: Hallucination Score. Lower is better for both.

Method	Qwen2.5-72B		Llama-3.3-70B
Method	MATH	AIME	MATH	AIME
Self-Consistency	$0.68$	$0.20$	$0.59$	$0.23$
Self-Verification	$0.66$	$0.15$	$0.56$	$0.19$
Pairwise Self-Verification	$0.69$	$0.15$	$0.59$	$0.24$
CD w/ ConGrs ( $\tau$ =0.5)	$0.68$	$0.20$	$0.61$	$0.23$
GSV w/ ConGrs ( $\kappa$ =0.7)	$0.70$	$0.20$	$0.65$	$0.27$

Table 3: Guided self-verification (GSV) with ConGrs consistently outperforms Self-Consistency and Self-Verification. Pass@

m

is an upper bound, as is QwQ-32B, a more expensive reasoning model specifically trained to excel at similar tasks.

Appendix figures & tables19 assets

Supplementary material from the paper’s appendix.

Appendix

LM Judge	FActScore	#T	#F	R
ConGrs (0.3, Qwen3-8B Judge)	0.70	20.73	6.95	0.93
ConGrs (0.5, Qwen3-8B Judge)	0.76	17.44	3.50	0.93
ConGrs (0.3)	0.70	20.81	6.97	0.93
ConGrs (0.5)	0.77	17.48	3.48	0.85

Appendix

Table 4: Ablation results for Qwen2.5-72B comparing different LM judges. We report FActScore, number of supported (#T) and unsupported facts (#F), and response ratio (R) averaged across the

100

entities.

Mean statistics $\bm{\rightarrow}$	# Nodes	%C	%D	C	D	C
				# Words		# Branches
Biographies	$27.50$	27	73	$7.70$	$25.71$	$2.39$
Long-form PopQA	$25.41$	27	73	$5.38$	$20.12$	$2.11$
False Presuppositions	$15.84$	11	89	$2.40$	$2.22$	$0.55$
Scientific References	$93.22$	3	97	$3.09$	$25.83$	$1.70$
Historical Events	$21.27$	35	65	$14.29$	$17.95$	$1.95$

Appendix

Table 5: Statistics for ConGrs constructed from five Qwen2.5-72B-Instruct responses per evaluation example, averaged across nodes in each ConGr and averaged across examples. C: consensus nodes, D: disagreement nodes.

Figure 6: Consensus decoding synthesizes responses by traversing a ConGr and selecting nodes that are present in at least a

\tau

fraction of responses, where

\tau\in[0,1]

is a hyperparameter (

\tau=0.5

in this example). The selected nodes’ text labels are concatenated and processed by a secondary LM to produce a coherent response (top). When this is not possible, the result is an abstention (bottom).

Dataset	Time (s)
Biographies	33
PopQA	38
Scientific Attributions	31
False Presuppositions	3
Historical Events	28
MATH	150

Appendix

Table 6: Mean combined runtime per example for ConGr construction (§ 2 ) and decoding experiments (§ 4 ).

Table 13

	Qwen2.5-72B	Qwen2.5-7B
	Llama-3.3-70B	Llama-3.1-8B
	OLMo-2-32B	OLMo-2-7B
Quantization	8-bit	n/a
Temperature	0.9	0.9
samples_per_prompt	5	5
max_new_tokens	500	500

Appendix

Table 9: Hyperparameters for response generation for factuality and refusal experiments.

$\bm{\tau}$	Model	FActScore Abstained Entities	FActScore All entities
0.3	Qwen2.5-72B	0.31	0.68
0.3	Qwen2.5-7B	0.34	0.68
0.5	Qwen2.5-72B	0.20	0.64
0.5	Qwen2.5-7B	0.28	0.64

Appendix

Table 10: Mean FActScore of original responses for entities that consensus decoding abstains on, compared to FActScore on all entities. Consensus decoding abstains on responses that are highly likely to contain hallucinations.

	Qwen2.5-72B				Llama-3.3-70B				OLMo-2-32B
Method	FActScore	#T	#F	R	FActScore	#T	#F	R	FActScore	#T	#F	R
Greedy	0.677 0.002	18.771 0.192	8.553 0.149	0.974 0.005	0.645 0.073	16.343 2.965	6.271 0.532	0.620 0.115	0.749 0.005	24.338 0.303	7.592 0.226	0.998 0.005
Mean of $m$	0.681 0.005	19.209 0.146	8.455 0.156	0.966 0.007	0.641 0.007	16.420 0.565	6.487 0.129	0.589 0.016	0.740 0.014	25.958 0.274	7.764 0.384	0.976 0.006
Shortest	0.689 0.009	19.018 0.338	8.121 0.258	0.952 0.004	0.692 0.023	16.989 0.551	4.931 0.427	0.482 0.027	0.765 0.011	25.864 0.710	7.372 0.266	0.950 0.014
LM consensus	0.693 0.010	20.925 0.330	8.979 0.448	0.974 0.005	0.687 0.014	19.966 0.299	6.587 0.318	0.618 0.019	0.757 0.005	25.380 0.405	7.998 0.224	0.994 0.009
MBR	0.696 0.006	19.469 0.097	7.984 0.333	0.962 0.007	0.676 0.014	17.505 0.359	5.779 0.592	0.566 0.017	0.756 0.006	25.650 0.652	8.122 0.405	0.988 0.013

Appendix

Table 11: Results for biography generation: FActScore, numbers of supported (#T) and unsupported (#F) facts, and response ratio (R, how often the model doesn’t abstain). We report mean values over five replications. Standard deviation across runs is in small font.

	Qwen2.5-72B				Llama-3.3-70B				OLMo-2-32B
Method	FActScore	#T	#F	R	FActScore	#T	#F	R	FActScore	#T	#F	R
Greedy	0.684 0.006	18.652 0.402	8.184 0.108	0.990 0.010	0.620 0.007	15.804 0.183	8.296 0.059	0.840 0.007	0.738 0.005	23.096 0.155	7.502 0.066	0.984 0.009
Mean of $m$	0.694 0.006	18.720 0.705	8.096 0.104	0.956 0.011	0.626 0.015	15.548 0.538	8.720 0.209	0.814 0.015	0.746 0.006	24.354 0.226	7.838 0.073	0.982 0.011
Shortest	0.714 0.006	19.184 0.378	7.344 0.273	0.958 0.005	0.644 0.006	14.724 0.419	7.322 0.301	0.716 0.009	0.752 0.008	23.930 0.116	7.366 0.343	0.974 0.006
LM consensus	0.722 0.005	21.708 0.062	8.270 0.313	0.980 0.010	0.684 0.011	17.238 0.712	8.418 0.072	0.878 0.008	0.762 0.013	26.146 0.717	7.186 0.413	0.990 0.014
MBR	0.712 0.013	19.616 0.268	7.368 0.259	0.968 0.008	0.656 0.013	13.910 1.110	7.908 0.043	0.836 0.009	0.762 0.008	25.388 1.170	7.282 0.267	0.958 0.034

Appendix

Table 12: Results for PopQA . We report FActScore ( Min et al., 2023 ) , number of supported (#T) and unsupported (#F) facts, and response ratio (R, how often the model responds and doesn’t abstain). Like in Table 11 , consensus decoding with

\tau=0.3

consistently improves FActScore by decreasing the number of unsupported facts. We report mean values over five replications. Standard deviation across runs is in small font.

	Qwen2.5-7B				Llama-3.1-8B				OLMo-2-7B
Method	FActScore	#T	#F	R	FActScore	#T	#F	R	FActScore	#T	#F	R
Greedy	0.68	18.40	8.27	0.98	0.85	15.24	2.28	0.72	0.60	22.71	14.03	1.00
Mean of $m$	0.56	16.02	11.69	0.99	0.78	19.96	4.77	0.76	0.59	24.23	14.56	0.99
Shortest	0.57	15.81	11.13	0.99	0.81	20.21	4.10	0.71	0.58	22.35	13.80	0.98
LM Consensus	0.58	18.43	13.03	1.00	0.67	19.64	7.00	0.64	0.64	24.69	13.33	1.00
MBR	0.56	15.76	11.35	1.00	0.81	20.60	4.24	0.75	0.60	22.08	13.42	1.00

Appendix

Table 13: Results for Biography generation . We report FActScore ( Min et al., 2023 ) , numbers of supported (#T) and unsupported (#F) facts, and response ratio (R, how often the model responds and doesn’t abstain) for smaller models. Consensus decoding with

\tau=0.3

consistently improves FActScore by decreasing the number of unsupported facts. Using a threshold of

\tau=0.5

further improves FActScore by filtering more facts, at the expense of the total number of facts.

Method	Qwen2.5-7B				Llama-3.1-8B				OLMo-2-7B
Method	FActScore	#T	#F	R	FActScore	#T	#F	R	FActScore	#T	#F	R
Greedy	0.55	15.11	11.74	0.99	0.66	16.06	7.92	0.86	0.60	19.76	12.59	0.98
Mean of $m$	0.52	14.33	12.69	0.99	0.65	16.11	8.27	0.82	0.59	20.36	13.82	0.98
Shortest	0.56	14.86	11.87	0.99	0.65	15.93	7.60	0.73	0.58	19.67	13.93	0.97
LM Consensus	0.61	17.67	10.97	0.96	0.72	20.25	7.77	0.87	0.70	23.47	9.84	0.99
MBR	0.51	13.91	12.47	0.96	0.69	17.06	7.19	0.83	0.62	20.33	12.30	0.98

Appendix

Table 14: Results for PopQA . We report FActScore ( Min et al., 2023 ) , number of supported (#T) and unsupported (#F) facts, and response ratio (R, how often the model responds and doesn’t abstain) for smaller models. Like in Table 13 , consensus decoding with

\tau=0.3

consistently improves FActScore by decreasing the number of unsupported facts.

Method	Qwen2.5-72B		Qwen2.5-7B		Llama-3.3-70B		Llama-3.1-8B		OLMo-2-32B		OLMo-2-7B
Method	R $\downarrow$	H $\downarrow$	R $\downarrow$	H $\downarrow$	R $\downarrow$	H $\downarrow$	R $\downarrow$	H $\downarrow$	R $\downarrow$	H $\downarrow$	R $\downarrow$	H $\downarrow$
Greedy	0.008	0.008	0.064	0.064	0	0	0	0	0.280	0.280	0.004	0.004
Mean of $m$	0.008	0.008	0.056	0.056	0.0008	0.0008	0.0032	0.0032	0.252	0.252	0.0064	0.0064
Shortest	0.008	0.008	0.024	0.024	0	0	0	0	0.148	0.148	0.004	0.004
LM Consensus	0.012	0.012	0.056	0.056	0.004	0.004	0	0	0.312	0.312	0.004	0.004
MBR	0.008	0.008	0.040	0.040	0.004	0.004	0	0	0.200	0.200	0.004	0.004

Appendix

Table 15: Performance on the Historical Events task from HALoGEN ( Ravichander et al., 2025 ) . We report Response Ratio (R

\downarrow

) and Hallucination Score (H

\downarrow

), both lower is better. Consensus decoding with ConGrs consistently achieves low Response Ratio and Hallucination Score for the OLMo model family.

	False Presuppositions						Scientific References
	Qwen2.5-7B		Llama-3.1-8B		OLMo-2-7B		Qwen2.5-7B		Llama-3.1-8B		OLMo-2-7B
Method	R $\downarrow$	H $\downarrow$	R $\downarrow$	H $\downarrow$	R $\downarrow$	H $\downarrow$	R $\downarrow$	H $\downarrow$	R $\downarrow$	H $\downarrow$	R $\downarrow$	H $\downarrow$
Greedy	0.40	0.28	0.60	0.45	0.51	0.41	0.56	0.49	0.42	0.33	0.89	0.81
Mean of $m$	0.41	0.30	0.61	0.47	0.51	0.42	0.67	0.62	0.49	0.43	0.88	0.82
Shortest	0.36	0.25	0.50	0.34	0.54	0.46	0.49	0.45	0.29	0.25	0.77	0.71
LM Consensus	0.48	0.36	0.69	0.55	0.76	0.63	0.05	0.04	0.15	0.13	0.05	0.04

Appendix

Table 16: Performance on the False Presuppositions and Scientific References tasks from HALoGEN when synthesizing responses from small model sizes. We report Response Ratio (R

\downarrow

) and Hallucination Score (H

\downarrow

), both lower is better. Consensus decoding with ConGrs consistently achieves low Response Ratio and Hallucination Score.

Method	FActScore	#T	#F	R
Beam Search	0.68	18.31	8.10	0.97
Diverse Beam Search	0.67	18.65	8.30	0.98
Range Voting (Beam Search)	0.69	19.39	8.14	0.97
ConGrs ( $\tau=0.3$ )	0.70	20.81	6.97	0.93
ConGrs ( $\tau=0.5$ )	0.77	17.48	3.48	0.85

Appendix

Table 17: Comparison of consensus decoding performance with beam search variants (all decoding-time algorithms). Results are using Qwen2.5-72B on biography generation. Consensus decoding with

\tau=0.3

outperforms all variants in terms of FActScore and number of supported/unsupported claims, with only a minor decrease in response ratio.

Temperature	% Degenerate	% Stopword-only	Mean #words/node
0.9	7	28	7.70
1.2	3	41	5.25
1.4	5	37	5.84
1.6	8	43	5.59
1.8	6	43	5.14
2.0	8	44	4.49

Appendix

Table 18: ConGrs construction statistics for Qwen2.5-72B at different temperatures. We report the percentage of degenerate graphs (with

\leq 1

consensus node), the percentage of stopword-only consensus nodes, and the mean number of words per consensus node.

Temperature	R ( $\tau=0.3$ )	R ( $\tau=0.5$ )
0.9	0.92	0.85
1.2	0.89	0.80
1.4	0.88	0.81
1.6	0.86	0.79
1.8	0.82	0.77
2.0	0.83	0.75

Appendix

Table 19: Response rate (R) for Qwen2.5-72B at different temperatures and ConGrs thresholds

\tau

= 0.3, 0.5, averaged across the

100

entities.

Temperature	Threshold $\tau$	FActScore	#T	#F
1.2	ConGrs (0.3)	0.74	20.58	5.25
	ConGrs (0.5)	0.84	16.20	2.65
1.4	ConGrs (0.3)	0.75	21.54	5.25
	ConGrs (0.5)	0.84	16.98	2.35
1.6	ConGrs (0.3)	0.76	21.45	5.43
	ConGrs (0.5)	0.82	16.35	2.57

Appendix

Table 20: Ablation results for Qwen2.5-72B at different temperatures and ConGrs thresholds

\tau

= 0.3, 0.5. We report FActScore, number of supported (#T) and unsupported facts (#F), averaged across the

100

entities.

Temperature	Threshold $\tau$	FActScore	#T	#F	R
0.9	ConGrs (0.1)	0.47	20.80	30.36	1.00
	ConGrs (0.2)	0.49	16.72	14.52	1.00
	ConGrs (0.3)	0.67	13.86	4.81	0.84
	ConGrs (0.4)	0.75	11.90	2.90	0.84
	ConGrs (0.5)	0.79	11.85	2.20	0.80
	ConGrs (0.7)	0.81	9.58	1.74	0.76

Appendix

Table 21: Ablation results for Qwen2.5-72B (

m=10

responses) at different temperatures and ConGrs thresholds

\tau

. We report FActScore, number of supported (#T) and unsupported facts (#F), and response ratio (R) averaged across the

25

sampled entities.

Figure 7: Different selection thresholds for Consensus Decoding are better for different kinds of entities. Generated biographies for very frequent entities are often very factual and benefit from a permissive, low value of

\tau

. On the other hand, generated biographies for very rare entities benefit from a high value of

\tau

, which only aggregates spans of text that occur in the vast majority of responses.

Text Generation

Text generation studies methods for producing coherent, useful language from prompts, data, and dialogue context.

See all 422 papers

Correct Prediction, Wrong Steps? Consensus Reasoning Knowledge Graph for Robust Chain-of-Thought Synthesis
Apr 15, 2026Zipeng Ling, Shuliang Liu, Seonil Son +4Reasoning Trace Analysis Logical Reasoning
The Hong Kong University of Science and Technology (Guangzhou) · University of Alberta · Alberta Machine Intelligence Institute +3
Reasoning Consensus: Structural Ensembling of LLM Reasoning via Weighted DAG Aggregation
Jul 30, 2026Amruta Parulekar, Jinu Lee, Dilek Hakkani-Tür +1Structured Reasoning LLM Reasoning with Graphs
University of Illinois Urbana-Champaign
Simulating Respondents, Not Single Questions: Coherent Survey Generation with Large Language Models
Sep 28, 2026Ji Huang, Mengfei Li, Shuai ShaoLarge Language Model-Based Social Simulation Conditional Generative Modeling
School of Computer Science, University of Science and Technology of China · School of Management, Fudan University

Apr 15, 2026J/K move · Enter open · S save

Correct Prediction, Wrong Steps? Consensus Reasoning Knowledge Graph for Robust Chain-of-Thought Synthesis

Zipeng Ling, Shuliang Liu, Seonil Son, Shenghong Fu+3

The Hong Kong University of Science and Technology (Guangzhou) · University of Alberta · Alberta Machine Intelligence Institute+3

Reasoning Trace Analysis Logical Reasoning Self-Consistency Decoding CoT Reasoning Mathematical Reasoning Structured Reasoning+3

Open paper AskPDF arXiv

Large language models (LLMs) have become increasingly used for various tasks, often coupled with Chain-of-Thought (CoT) prompting to boost accuracy. Recent work has shown that high label-prediction accuracy does not guarantee correct intermediate reasoning, and the causes of reasoning flaws vary from sample to sample, yet existing remedies either focus on a single domain or assume that one flaw type applies uniformly across samples. A simple mitigation method is to provide the model with the correct answer, but we show that this yields no consistent improvement in reasoning quality. This indicates that the problem cannot be fixed by LLMs' awareness of answers, and must instead be addressed through the structure of reasoning. Motivated by this, we propose CRAFT (Consensus Reasoning knowledge graph Aggregation for Flaw-aware Trace synthesis), which aggregates the consensus components shared across multiple candidate reasoning traces to synthesize improved ones. CRAFT consistently improves label-prediction accuracy on both logical and mathematical reasoning benchmarks, outperforming most baselines, while its post-processed traces achieve higher quality under fine-grained benchmark evaluation.

Abstract

Text Generation

Explore similar work

Correct Prediction, Wrong Steps? Consensus Reasoning Knowledge Graph for Robust Chain-of-Thought Synthesis

Reasoning Consensus: Structural Ensembling of LLM Reasoning via Weighted DAG Aggregation

Simulating Respondents, Not Single Questions: Coherent Survey Generation with Large Language Models