Author name cluster

Kyomin Jung

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

18 papers

2 author rows

AAAI Conference 2026 Conference Paper

Confidence-Guided Stepwise Model Routing for Cost-Efficient Reasoning

Sangmook Lee
Dohyung Kim
Hyukhun Koh
Nakyeong Yang
Kyomin Jung

Recent advances in Large Language Models (LLMs) - particularly model scaling and test-time techniques - have greatly enhanced the reasoning capabilities of language models at the expense of higher inference costs. To lower inference costs, prior works train router models or deferral mechanisms that allocate easy queries to a small, efficient model, while forwarding harder queries to larger, more expensive models. However, these trained router models often lack robustness under domain shifts and require expensive data synthesis techniques such as Monte Carlo rollouts to obtain sufficient ground-truth routing labels for training. In this work, we propose Confidence-Guided Stepwise Model Routing for Cost-Efficient Reasoning (STEER), a domain-agnostic, framework that performs fine-grained, step-level routing between smaller and larger LLMs without utilizing external models. STEER leverages confidence scores from the smaller model’s logits prior to generating a reasoning step, so that the large model is invoked only when necessary. Extensive evaluations using different LLMs on a diverse set of challenging benchmarks across multiple domains such as Mathematical Reasoning, Multi-Hop QA, and Planning tasks indicate that STEER achieves competitive or enhanced accuracy while reducing inference costs (up to +20% accuracy with 48% less FLOPs compared to solely using the larger model on AIME), outperforming baselines that rely on trained external modules. Our results establish model-internal confidence as a robust, domain-agnostic signal for model routing, offering a scalable pathway for efficient LLM deployment.

PDF Details DOI

ICLR Conference 2025 Conference Paper

Guaranteed Generation from Large Language Models

Minbeom Kim
Thibaut Thonet
Jos Rozen
Hwaran Lee
Kyomin Jung
Marc Dymetman

As large language models (LLMs) are increasingly used across various applications, there is a growing need to control text generation to satisfy specific constraints or requirements. This raises a crucial question: Is it possible to guarantee strict constraint satisfaction in generated outputs while preserving the distribution of the original model as much as possible? We first define the ideal distribution — the one closest to the original model, which also always satisfies the expressed constraint — as the ultimate goal of guaranteed generation. We then state a fundamental limitation, namely that it is impossible to reach that goal through autoregressive training alone. This motivates the necessity of combining training-time and inference-time methods to enforce such guarantees. Based on this insight, we propose GUARD, a simple yet effective approach that combines an autoregressive proposal distribution with rejection sampling. Through GUARD’s theoretical properties, we show how controlling the KL divergence between a specific proposal and the target ideal distribution simultaneously optimizes inference speed and distributional closeness. To validate these theoretical concepts, we conduct extensive experiments on two text generation settings with hard-to-satisfy constraints: a lexical constraint scenario and a sentiment reversal scenario. These experiments show that GUARD achieves perfect constraint satisfaction while almost preserving the ideal distribution with highly improved inference efficiency. GUARD provides a principled approach to enforcing strict guarantees for LLMs without compromising their generative capabilities.

Details

NeurIPS Conference 2025 Conference Paper

Program Synthesis via Test-Time Transduction

Kang-il Lee
Jahyun Koo
Seunghyun Yoon
Minbeom Kim
Hyukhun Koh
Dongryeol Lee
Kyomin Jung

We introduce transductive program synthesis, a new formulation of the program synthesis task that explicitly leverages test inputs during synthesis. While prior approaches to program synthesis--whether based on natural language descriptions or input-output examples--typically aim to generalize from training examples, they often struggle with robustness, especially in real-world settings where training examples are limited and test inputs involve various edge cases. To address this, we propose a novel framework that improves robustness by treating synthesis as an active learning over a finite hypothesis class defined by programs' outputs. We use an LLM to predict outputs for selected test inputs and eliminate inconsistent hypotheses, where the inputs are chosen via a greedy maximin algorithm to minimize the number of LLM queries required. We evaluate our approach on four benchmarks: Playgol, MBPP+, 1D-ARC, and programmatic world modeling on MiniGrid. We demonstrate that our method significantly improves program synthesis in both accuracy and efficiency. We release our code at https: //github. com/klee972/SYNTRA.

PDF Details

AIIM Journal 2024 Journal Article

Leveraging VQ-VAE tokenization for autoregressive modeling of medical time series

Yoonhyung Lee
Younhyung Chae
Kyomin Jung

In this work, we present CodeAR, a medical time series generative model for electronic health record (EHR) synthesis. CodeAR employs autoregressive modeling on discrete tokens obtained using a vector quantized-variational autoencoder (VQ-VAE), which addresses key challenges of accurate distribution modeling and patient privacy preservation in the medical domain. The proposed model is trained with next-token prediction instead of a regression problem for more accurate distribution modeling, where the autoregressive property of CodeAR is useful to capture the inherent causality in time series data. In addition, the compressive property of the VQ-VAE prevents CodeAR from memorizing the original training data, which ensures patient privacy. Experimental results demonstrate that CodeAR outperforms the baseline autoregressive-based and GAN-based models in terms of maximum mean discrepancy (MMD) and Train on Synthetic, Test on Real tests. Our results highlight the effectiveness of autoregressive modeling on discrete tokens, the utility of CodeAR in causal modeling, and its robustness against data memorization.

Details DOI

ICLR Conference 2021 Conference Paper

Bidirectional Variational Inference for Non-Autoregressive Text-to-Speech

Yoonhyung Lee
Joongbo Shin
Kyomin Jung

Although early text-to-speech (TTS) models such as Tacotron 2 have succeeded in generating human-like speech, their autoregressive architectures have several limitations: (1) They require a lot of time to generate a mel-spectrogram consisting of hundreds of steps. (2) The autoregressive speech generation shows a lack of robustness due to its error propagation property. In this paper, we propose a novel non-autoregressive TTS model called BVAE-TTS, which eliminates the architectural limitations and generates a mel-spectrogram in parallel. BVAE-TTS adopts a bidirectional-inference variational autoencoder (BVAE) that learns hierarchical latent representations using both bottom-up and top-down paths to increase its expressiveness. To apply BVAE to TTS, we design our model to utilize text information via an attention mechanism. By using attention maps that BVAE-TTS generates, we train a duration predictor so that the model uses the predicted duration of each phoneme at inference. In experiments conducted on LJSpeech dataset, we show that our model generates a mel-spectrogram 27 times faster than Tacotron 2 with similar speech quality. Furthermore, our BVAE-TTS outperforms Glow-TTS, which is one of the state-of-the-art non-autoregressive TTS models, in terms of both speech quality and inference speed while having 58% fewer parameters.

Details

AAAI Conference 2021 Conference Paper

Neural Sequence-to-grid Module for Learning Symbolic Rules

Segwang Kim
Hyoungwook Nam
Joonyoung Kim
Kyomin Jung

Logical reasoning tasks over symbols, such as learning arithmetic operations and computer program evaluations, have become challenges to deep learning. In particular, even stateof-the-art neural networks fail to achieve out-of-distribution (OOD) generalization of symbolic reasoning tasks, whereas humans can easily extend learned symbolic rules. To resolve this difficulty, we propose a neural sequence-to-grid (seq2grid) module, an input preprocessor that automatically segments and aligns an input sequence into a grid. As our module outputs a grid via a novel differentiable mapping, any neural network structure taking a grid input, such as ResNet or TextCNN, can be jointly trained with our module in an end-to-end fashion. Extensive experiments show that neural networks having our module as an input preprocessor achieve OOD generalization on various arithmetic and algorithmic problems including number sequence prediction problems, algebraic word problems, and computer program evaluation problems while other state-of-the-art sequence transduction models cannot. Moreover, we verify that our module enhances TextCNN to solve the bAbI QA tasks without external memory.

PDF Details

AAAI Conference 2020 Conference Paper

Improving Context-Aware Neural Machine Translation Using Self-Attentive Sentence Embedding

Hyeongu Yun
Yongkeun Hwang
Kyomin Jung

Fully Attentional Networks (FAN) like Transformer (Vaswani et al. 2017) has shown superior results in Neural Machine Translation (NMT) tasks and has become a solid baseline for translation tasks. More recent studies also have reported experimental results that additional contextual sentences improve translation qualities of NMT models (Voita et al. 2018; Müller et al. 2018; Zhang et al. 2018). However, those studies have exploited multiple context sentences as a single long concatenated sentence, that may cause the models to suffer from inefﬁcient computational complexities and long-range dependencies. In this paper, we propose Hierarchical Context Encoder (HCE) that is able to exploit multiple context sentences separately using the hierarchical FAN structure. Our proposed encoder ﬁrst abstracts sentence-level information from preceding sentences in a self-attentive way, and then hierarchically encodes context-level information. Through extensive experiments, we observe that our HCE records the best performance measured in BLEU score on English-German, English-Turkish, and English-Korean corpus. In addition, we observe that our HCE records the best performance in a crowd-sourced test set which is designed to evaluate how well an encoder can exploit contextual information. Finally, evaluation on English-Korean pronoun resolution test suite also shows that our HCE can properly exploit contextual information.

PDF Details

AAAI Conference 2019 Conference Paper

Detecting Incongruity between News Headline and Body Text via a Deep Hierarchical Encoder

Seunghyun Yoon
Kunwoo Park
Joongbo Shin
Hongjun Lim
Seungpil Won
Meeyoung Cha
Kyomin Jung

Some news headlines mislead readers with overrated or false information, and identifying them in advance will better assist readers in choosing proper news stories to consume. This research introduces million-scale pairs of news headline and body text dataset with incongruity label, which can uniquely be utilized for detecting news stories with misleading headlines. On this dataset, we develop two neural networks with hierarchical architectures that model a complex textual representation of news articles and measure the incongruity between the headline and the body text. We also present a data augmentation method that dramatically reduces the text input size a model handles by independently investigating each paragraph of news stories, which further boosts the performance. Our experiments and qualitative evaluations demonstrate that the proposed methods outperform existing approaches and efficiently detect news stories with misleading headlines in the real world.

PDF Details

AAAI Conference 2019 Conference Paper

Improving Neural Question Generation Using Answer Separation

Yanghoon Kim
Hwanhee Lee
Joongbo Shin
Kyomin Jung

Neural question generation (NQG) is the task of generating a question from a given passage with deep neural networks. Previous NQG models suffer from a problem that a significant proportion of the generated questions include words in the question target, resulting in the generation of unintended questions. In this paper, we propose answer-separated seq2seq, which better utilizes the information from both the passage and the target answer. By replacing the target answer in the original passage with a special token, our model learns to identify which interrogative word should be used. We also propose a new module termed keyword-net, which helps the model better capture the key information in the target answer and generate an appropriate question. Experimental results demonstrate that our answer separation method significantly reduces the number of improper questions which include answers. Consequently, our model significantly outperforms previous state-of-the-art NQG models.

PDF Details

AAAI Conference 2019 Conference Paper

Number Sequence Prediction Problems for Evaluating Computational Powers of Neural Networks

Hyoungwook Nam
Segwang Kim
Kyomin Jung

Inspired by number series tests to measure human intelligence, we suggest number sequence prediction tasks to assess neural network models’ computational powers for solving algorithmic problems. We define the complexity and difficulty of a number sequence prediction task with the structure of the smallest automaton that can generate the sequence. We suggest two types of number sequence prediction problems: the number-level and the digit-level problems. The number-level problems format sequences as 2-dimensional grids of digits and the digit-level problems provide a single digit input per a time step. The complexity of a number-level sequence prediction can be defined with the depth of an equivalent combinatorial logic, and the complexity of a digit-level sequence prediction can be defined with an equivalent state automaton for the generation rule. Experiments with number-level sequences suggest that CNN models are capable of learning the compound operations of sequence generation rules, but the depths of the compound operations are limited. For the digitlevel problems, simple GRU and LSTM models can solve some problems with the complexity of finite state automata. Memory augmented models such as Stack-RNN, Attention, and Neural Turing Machines can solve the reverse-order task which has the complexity of simple pushdown automaton. However, all of above cannot solve general Fibonacci, Arithmetic or Geometric sequence generation problems that represent the complexity of queue automata or Turing machines. The results show that our number sequence prediction problems effectively evaluate machine learning models’ computational capabilities.

PDF Details

ICML Conference 2015 Conference Paper

Double Nyström Method: An Efficient and Accurate Nyström Scheme for Large-Scale Data Sets

Woosang Lim
Minhwan Kim
Haesun Park
Kyomin Jung

The Nyström method has been one of the most effective techniques for kernel-based approach that scales well to large data sets. Since its introduction, there has been a large body of work that improves the approximation accuracy while maintaining computational efficiency. In this paper, we present a novel Nyström method that improves both accuracy and efficiency based on a new theoretical analysis. We first provide a generalized sampling scheme, CAPS, that minimizes a novel error bound based on the subspace distance. We then present our double Nyström method that reduces the size of the decomposition in two stages. We show that our method is highly efficient and accurate compared to other state-of-the-art Nyström methods by evaluating them on a number of real data sets.

Details

UAI Conference 2015 Conference Paper

Minimizing Expected Losses in Perturbation Models with Multidimensional Parametric Min-cuts

Adrian Kim
Kyomin Jung
Yongsub Lim
Daniel Tarlow
Pushmeet Kohli

We consider the problem of learning perturbation-based probabilistic models by computing and differentiating expected losses. This is a challenging computational problem that has traditionally been tackled using Monte Carlo-based methods. In this work, we show how a generalization of parametric min-cuts can be used to address the same problem, achieving higher accuracy and faster performance than a sampling-based baseline. Utilizing our proposed Skeleton Method, we show that we can learn the perturbation model so as to directly minimize expected losses. Experimental results show that this approach offers promise as a new way of training structured prediction models under complex loss functions.

Details

AAAI Conference 2010 Conference Paper

Coalitional Structure Generation in Skill Games

Yoram Bachrach
Reshef Meir
Kyomin Jung
Pushmeet Kohli

We consider optimizing the coalition structure in Coalitional Skill Games (CSGs), a succinct representation of coalitional games (Bachrach and Rosenschein 2008). In CSGs, the value of a coalition depends on the tasks its members can achieve. The tasks require various skills to complete them, and agents may have different skill sets. The optimal coalition structure is a partition of the agents to coalitions, that maximizes the sum of utilities obtained by the coalitions. We show that CSGs can represent any characteristic function, and consider optimal coalition structure generation in this representation. We provide hardness results, showing that in general CSGs, as well as in very restricted versions of them, computing the optimal coalition structure is hard. On the positive side, we show that the problem can be reformulated as constraint satisfaction on a hyper graph, and present an algorithm that finds the optimal coalition structure in polynomial time for instances with bounded tree-width and number of tasks.

PDF Details

NeurIPS Conference 2009 Conference Paper

Local Rules for Global MAP: When Do They Work ?

Kyomin Jung
Pushmeet Kohli
Devavrat Shah

We consider the question of computing Maximum A Posteriori (MAP) assignment in an arbitrary pair-wise Markov Random Field (MRF). We present a randomized iterative algorithm based on simple local updates. The algorithm, starting with an arbitrary initial assignment, updates it in each iteration by first, picking a random node, then selecting an (appropriately chosen) random local neighborhood and optimizing over this local neighborhood. Somewhat surprisingly, we show that this algorithm finds a near optimal assignment within $2n\ln n$ iterations on average and with high probability for {\em any} $n$ node pair-wise MRF with {\em geometry} (i. e. MRF graph with polynomial growth) with the approximation error depending on (in a reasonable manner) the geometric growth rate of the graph and the average radius of the local neighborhood -- this allows for a graceful tradeoff between the complexity of the algorithm and the approximation error. Through extensive simulations, we show that our algorithm finds extremely good approximate solutions for various kinds of MRFs with geometry.

PDF Details

SODA Conference 2009 Conference Paper

Transitive-closure spanners

Arnab Bhattacharyya 0001
Elena Grigorescu
Kyomin Jung
Sofya Raskhodnikova
David P. Woodruff

We define the notion of a transitive-closure spanner of a directed graph. Given a directed graph G = ( V, E ) and an integer k ≥ 1, a k-transitive-closure-spanner ( k-TC-spanner ) of G is a directed graph H = ( V, E H ) that has (1) the same transitive-closure as G and (2) diameter at most k. These spanners were studied implicitly in access control, property testing, and data structures, and properties of these spanners have been rediscovered over the span of 20 years. We bring these areas under the unifying framework of TC-spanners. We abstract the common task implicitly tackled in these diverse applications as the problem of constructing sparse TC-spanners. We study the approximability of the size of the sparsest k -TC-spanner for a given digraph. Our technical contributions fall into three categories: algorithms for general digraphs, inapproximability results, and structural bounds for a specific graph family which imply an efficient algorithm with a good approximation ratio for that family. Algorithms. We present two efficient deterministic algorithms that find k -TC-spanners of near optimal size. The first algorithm gives an -approximation for k > 2. Our method, based on a combination of convex programming and sampling, yields the first sublinear approximation ratios for (1) D irected k -S panner, a well-studied generalization of k -TC-S panner, and (2) its variants C lient /S erver D irected k -S panner, and the k -D iameter S panning S ubgraph. This resolves the main open question of Elkin and Peleg (IPCO, 2001). The second algorithm, specific to the k -TC-spanner problem, gives an -approximation. It shows that for, our problem has a provably better approximation ratio than D irected k -S panner and its variants. This algorithm also resolves an open question of Hesse (SODA, 2003).

Details

AIJ Journal 2008 Journal Article

Phase transition in a random NK landscape model

Sung-Soon Choi
Kyomin Jung
Jeong Han Kim

An analysis for the phase transition in a random NK landscape model, NK ( n, k, z ), is given. This model is motivated from population genetics and the solubility problem for the model is equivalent to a random ( k + 1 ) -SAT problem. Gao and Culberson [Y. Gao, J. Culberson, An analysis of phase transition in NK landscapes, Journal of Artificial Intelligence Research 17 (2002) 309–332] showed that a random instance generated by NK ( n, 2, z ) with z > z 0 = 27 − 7 5 4 is asymptotically insoluble. Based on empirical results, they conjectured that the phase transition occurs around the value z = z 0. We prove that an instance generated by NK ( n, 2, z ) with z < z 0 is soluble with positive probability by providing a polynomial time algorithm. Using branching process arguments, we prove again that an instance generated by NK ( n, 2, z ) with z > z 0 is asymptotically insoluble. The results show the phase transition around z = z 0 for NK ( n, 2, z ). In the course of the analysis, we introduce a generalized random 2-SAT formula, which is of self interest, and show its phase transition phenomenon.

Details DOI

NeurIPS Conference 2007 Conference Paper

Local Algorithms for Approximate Inference in Minor-Excluded Graphs

Kyomin Jung
Devavrat Shah

We present a new local approximation algorithm for computing MAP and log-partition function for arbitrary exponential family distribution represented by a finite-valued pair-wise Markov random field (MRF), say G. Our algorithm is based on decomposing G into appropriately chosen small components; computing estimates locally in each of these components and then producing a good global solution. We prove that the algorithm can provide approximate solution within arbitrary accuracy when $G$ excludes some finite sized graph as its minor and G has bounded degree: all Planar graphs with bounded degree are examples of such graphs. The running time of the algorithm is $\Theta(n)$ (n is the number of nodes in G), with constant dependent on accuracy, degree of graph and size of the graph that is excluded as a minor (constant for Planar graphs). Our algorithm for minor-excluded graphs uses the decomposition scheme of Klein, Plotkin and Rao (1993). In general, our algorithm works with any decomposition scheme and provides quantifiable approximation guarantee that depends on the decomposition scheme.

PDF Details

STOC Conference 2007 Conference Paper

Stability of the max-weight routing and scheduling protocol in dynamic networks and at critical loads

Matthew Andrews
Kyomin Jung
Alexander L. Stolyar

We study the stability of the max-weight protocol for combined routingand scheduling in communication networks. Previous work has shownthat this protocol is stable for adversarial multicommodity trafficin subcritically loaded static networks and for single-commoditytraffic in critically loaded dynamic networks. We show: The max-weight protocol is stable for adversarial multicommodity traffic in adversarial dynamic networks whenever the network is subcriticallyloaded. The max-weight protocol is stable for fixed multicommodity trafficin fixed networks even if the network is critically loaded. The latter result has implications for the running time of themax-weight protocol when it is used to solve multicommodity flowproblems. In particular, for a fixed problem instance we show thatif the value of the optimum solution is known, the max-weight protocolfinds a flow that is within a (1-ε)-factor of optimal in time O(1/ε) (improving the previous bound of O(1/ε 2 )). If thevalue of the optimum solution is not known, we show how to apply themax-weight algorithm in a binary search procedure that runs in O(1/ε) time.

Details